Skip to main content

Fundamental limitations on efficiently forecasting certain epidemic measures in network models

Author(s): Rosenkrantz, Daniel J; Vullikanti, Anil; Ravi, SS; Stearns, Richard E; Levin, Simon; et al

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorRosenkrantz, Daniel J-
dc.contributor.authorVullikanti, Anil-
dc.contributor.authorRavi, SS-
dc.contributor.authorStearns, Richard E-
dc.contributor.authorLevin, Simon-
dc.contributor.authorPoor, H Vincent-
dc.contributor.authorMarathe, Madhav V-
dc.identifier.citationRosenkrantz, Daniel J, Vullikanti, Anil, Ravi, SS, Stearns, Richard E, Levin, Simon, Poor, H Vincent, Marathe, Madhav V. (2022). Fundamental limitations on efficiently forecasting certain epidemic measures in network models. Proceedings of the National Academy of Sciences, 119 (4), 10.1073/pnas.2109228119en_US
dc.description.abstractThe 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.en_US
dc.relation.ispartofProceedings of the National Academy of Sciencesen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleFundamental limitations on efficiently forecasting certain epidemic measures in network modelsen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
Fundamental limitations on efficiently forecasting certain epidemic measures in network models. .pdf816.37 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.