TY - JOUR

T1 - Fundamental limitations on efficiently forecasting certain epidemic measures in network models

AU - Rosenkrantz, Daniel J.

AU - Vullikanti, Anil

AU - Ravi, S. S.

AU - Stearns, Richard E.

AU - Levin, Simon

AU - Poor, H. Vincent

AU - Marathe, Madhav V.

N1 - Funding Information:
ACKNOWLEDGMENTS. We sincerely thank to the referees for providing valuable feedback. We also thank members of the Biocomplexity COVID-19 Response Team and the Network Systems Science and Advanced Computing Division for their thoughtful comments and suggestions related to epidemic modeling and response support. We thank Jason Matheny, Naren Ramakrishnan, and Philippe Loustaunau for discussions on this topic during the IARPA Open Source Indicators project that led to the work. This work has been partially supported by Defense Threat Reduction Agency Contract HDTRA1-19-D-0007; University of Virginia Strategic Investment Fund Award SIF160; NIH Grants 1R01GM109718 and 2R01GM109718; and NSF Grants IIS-1633028 (Big Data), CMMI-1745207 (Early Concept Grants for Exploratory Research), OAC-1916805 (Cyberinfrastructure for Network Engineering and Science), CCF-1918656 (Expeditions), CNS-2028004 (Rapid Response Research [RAPID]), OAC-2027541 (RAPID), IIS-2026982 (RAPID), IIS-1908530, IIS-1955797, and IIS-2027848. The US Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon.
Publisher Copyright:
© 2022 National Academy of Sciences. All rights reserved.

PY - 2022/1/25

Y1 - 2022/1/25

N2 - The ongoing COVID-19 pandemic underscores the importance of developing reliable forecasts that would allow decision makers to devise appropriate response strategies. Despite much recent research on the topic, epidemic forecasting remains poorly understood. Researchers have attributed the difficulty of forecasting contagion dynamics to a multitude of factors, including complex behavioral responses, uncertainty in data, the stochastic nature of the underlying process, and the high sensitivity of the disease parameters to changes in the environment. We offer a rigorous explanation of the difficulty of short-term forecasting on networked populations using ideas from computational complexity. Specifically, we show that several forecasting problems (e.g., the probability that at least a given number of people will get infected at a given time and the probability that the number of infections will reach a peak at a given time) are computationally intractable. For instance, efficient solvability of such problems would imply that the number of satisfying assignments of an arbitrary Boolean formula in conjunctive normal form can be computed efficiently, violating a widely believed hypothesis in computational complexity. This intractability result holds even under the ideal situation, where all the disease parameters are known and are assumed to be insensitive to changes in the environment. From a computational complexity viewpoint, our results, which show that contagion dynamics become unpredictable for both macroscopic and individual properties, bring out some fundamental difficulties of predicting disease parameters. On the positive side, we develop efficient algorithms or approximation algorithms for restricted versions of forecasting problems.

AB - The ongoing COVID-19 pandemic underscores the importance of developing reliable forecasts that would allow decision makers to devise appropriate response strategies. Despite much recent research on the topic, epidemic forecasting remains poorly understood. Researchers have attributed the difficulty of forecasting contagion dynamics to a multitude of factors, including complex behavioral responses, uncertainty in data, the stochastic nature of the underlying process, and the high sensitivity of the disease parameters to changes in the environment. We offer a rigorous explanation of the difficulty of short-term forecasting on networked populations using ideas from computational complexity. Specifically, we show that several forecasting problems (e.g., the probability that at least a given number of people will get infected at a given time and the probability that the number of infections will reach a peak at a given time) are computationally intractable. For instance, efficient solvability of such problems would imply that the number of satisfying assignments of an arbitrary Boolean formula in conjunctive normal form can be computed efficiently, violating a widely believed hypothesis in computational complexity. This intractability result holds even under the ideal situation, where all the disease parameters are known and are assumed to be insensitive to changes in the environment. From a computational complexity viewpoint, our results, which show that contagion dynamics become unpredictable for both macroscopic and individual properties, bring out some fundamental difficulties of predicting disease parameters. On the positive side, we develop efficient algorithms or approximation algorithms for restricted versions of forecasting problems.

KW - Computational complexity

KW - Epidemic measures

KW - Forecasting

KW - Network dynamics

UR - http://www.scopus.com/inward/record.url?scp=85123063044&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85123063044&partnerID=8YFLogxK

U2 - 10.1073/pnas.2109228119

DO - 10.1073/pnas.2109228119

M3 - Article

C2 - 35046025

AN - SCOPUS:85123063044

VL - 119

JO - Proceedings of the National Academy of Sciences of the United States of America

JF - Proceedings of the National Academy of Sciences of the United States of America

SN - 0027-8424

IS - 4

M1 - e2109228119

ER -