{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T03:49:15Z","timestamp":1776743355966,"version":"3.51.2"},"reference-count":70,"publisher":"Proceedings of the National Academy of Sciences","issue":"4","license":[{"start":{"date-parts":[[2022,1,19]],"date-time":"2022-01-19T00:00:00Z","timestamp":1642550400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"name":"NSF","award":["RAPID Grant IIS-2026982"],"award-info":[{"award-number":["RAPID Grant IIS-2026982"]}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2022,1,25]]},"abstract":"<jats:title>Significance<\/jats:title>\n          <jats:p>We show that under widely believed complexity theoretic hypotheses, one cannot expect to find provably correct and efficient algorithms for predicting epidemic dynamics on general networks. These results hold even under idealized problem formulations, where all the model parameters are known and are insensitive to changes in environment. Further, they hold even for a small time horizon with just one random parameter, namely, the transmission probability. Thus, computational complexity poses an inherent challenge to effective and efficient epidemic forecasting in network models. Our results do not rule out heuristics that work well in practice or algorithms that provide provable guarantees for restricted networks. Rather, they suggest that algorithms working across a range of inputs should exploit properties of problem instances.<\/jats:p>","DOI":"10.1073\/pnas.2109228119","type":"journal-article","created":{"date-parts":[[2022,1,19]],"date-time":"2022-01-19T22:20:37Z","timestamp":1642630837000},"update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":20,"title":["Fundamental limitations on efficiently forecasting certain epidemic measures in network models"],"prefix":"10.1073","volume":"119","author":[{"given":"Daniel J.","family":"Rosenkrantz","sequence":"first","affiliation":[{"name":"Biocomplexity Institute and Initiative, University of Virginia, Charlottesville, VA 22904"},{"name":"Department of Computer Science, University at Albany\u2013State University of New York, Albany, NY 12222"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anil","family":"Vullikanti","sequence":"additional","affiliation":[{"name":"Biocomplexity Institute and Initiative, University of Virginia, Charlottesville, VA 22904"},{"name":"Department of Computer Science, University of Virginia, Charlottesville, VA 22904"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[{"name":"Biocomplexity Institute and Initiative, University of Virginia, Charlottesville, VA 22904"},{"name":"Department of Computer Science, University at Albany\u2013State University of New York, Albany, NY 12222"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[{"name":"Biocomplexity Institute and Initiative, University of Virginia, Charlottesville, VA 22904"},{"name":"Department of Computer Science, University at Albany\u2013State University of New York, Albany, NY 12222"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8216-5639","authenticated-orcid":false,"given":"Simon","family":"Levin","sequence":"additional","affiliation":[{"name":"Department of Ecology and Evolutionary Biology, Princeton University, Princeton, NJ 08544"},{"name":"Princeton Environmental Institute, Princeton University, Princeton, NJ 08544"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2062-131X","authenticated-orcid":false,"given":"H. Vincent","family":"Poor","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1653-0658","authenticated-orcid":false,"given":"Madhav V.","family":"Marathe","sequence":"additional","affiliation":[{"name":"Biocomplexity Institute and Initiative, University of Virginia, Charlottesville, VA 22904"},{"name":"Department of Computer Science, University of Virginia, Charlottesville, VA 22904"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"341","published-online":{"date-parts":[[2022,1,19]]},"reference":[{"key":"e_1_3_4_1_2","unstructured":"Centers for Disease Control and Prevention COVID-19 forecasts: Cases (2021). https:\/\/www.cdc.gov\/coronavirus\/2019-ncov\/cases-updates\/forecasts-cases.html. Accessed 28 September 2021."},{"key":"e_1_3_4_2_2","unstructured":"Defense Advanced Research Projects Agency CHIKV Challenge announces winners progress toward forecasting the spread of infectious diseases (2015). https:\/\/www.darpa.mil\/news-events\/2015-05-27. Accessed 28 September 2021."},{"key":"e_1_3_4_3_2","doi-asserted-by":"crossref","unstructured":"S. Muthiah . \u201cEMBERS at 4 years: Experiences operating an open source indicators forecasting system\u201d in KDD\u201916: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining B. Krishnapuram . Eds. (Association for Computing Machinery New York 2016) pp. 205\u2013214.","DOI":"10.1145\/2939672.2939709"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1186\/1741-7015-10-165"},{"key":"e_1_3_4_5_2","doi-asserted-by":"crossref","unstructured":"P. Chakraborty . \u201cForecasting a moving target: Ensemble models for ILI case count predictions\u201d in Proceedings of the 2014 SIAM International Conference on Data Mining (SDM) M. Zaki . Eds. (Society for Industrial and Applied Mathematics Philadelphia 2014) pp. 262\u2013270.","DOI":"10.1137\/1.9781611973440.30"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-019-08616-0"},{"key":"e_1_3_4_7_2","doi-asserted-by":"crossref","unstructured":"T. Martin J. M. Hofman A. Sharma A. Anderson D. J. Watts \u201cExploring limits to prediction in complex social systems\u201d in Proceedings of the 25th International Conference on World Wide Web WWW 2016 J. Bourdeau J. Hendler R. Nkambou I. Horrocks B. Y. Zhao Eds. (Association for Computing Machinery 2016) pp. 683\u2013694.","DOI":"10.1145\/2872427.2883001"},{"key":"e_1_3_4_8_2","doi-asserted-by":"crossref","unstructured":"S. Krishnan P. Butler R. Tandon J. Leskovec N. Ramakrishnan \u201cSeeing the forest for the trees: New approaches to forecasting cascades\u201d in WebSci\u201916: Proceedings of the 8th ACM Conference on Web Science WebSci 2016 W. Nejdl W. Hall P. Parigi S. Staab Eds. (Association for Computing Machinery New York 2016) pp. 249\u2013258.","DOI":"10.1145\/2908131.2908155"},{"key":"e_1_3_4_9_2","unstructured":"N. Ramakrishnan . \u201c\u2018Beating the news\u2019 with EMBERS: Forecasting civil unrest using open source indicators\u201d in KDD\u201914: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining S. A. Macskassy C. Perlich J. Leskovec W. Wang R. Ghani Eds. (Association for Computing Machinery New York 2014) pp. 1799\u20131808."},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.860134"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.275.5306.1616"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.355.6324.468"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.355.6324.468"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aal3856"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aal2887"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aam7032"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature07634"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1248506"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pmed.0020144"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pmed.0030003"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1822167116"},{"key":"e_1_3_4_22_2","unstructured":"B. Resnick Why it\u2019s so hard to see into the future of COVID-19. Vox (2020). https:\/\/www.vox.com\/science-and-health\/2020\/4\/10\/21209961\/coronavirus-models-covid-19-limitations-imhe. Accessed 27 September 2021."},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1038\/d41586-020-01003-6"},{"key":"e_1_3_4_24_2","unstructured":"The COVID-19 Forecast Hub community. https:\/\/covid19forecasthub.org\/. Accessed 30 December 2021."},{"key":"e_1_3_4_25_2","doi-asserted-by":"crossref","unstructured":"J. Cheng L. A. Adamic J. M. Kleinberg J. Leskovec \u201cDo cascades recur?\u201d in Proceedings of the 25th International Conference on World Wide Web WWW 2016 J. Bourdeau J. Hendler R. Nkambou I. Horrocks B. Y. Zhao Eds. (Association for Computing Machinery 2016) pp. 671\u2013681.","DOI":"10.1145\/2872427.2882993"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pbio.3000897"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms3837"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1186\/s12879-016-1669-x"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tree.2006.03.013"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1890\/ES11-00211.1"},{"key":"e_1_3_4_31_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman and Co., San Francisco, 1979)."},{"key":"e_1_3_4_32_2","first-page":"525","article-title":"On the predictability of coupled automata: An allegory about chaos","volume":"5","author":"Buss S. R.","year":"1991","unstructured":"S. R. Buss, C. H. Papadimitriou, J. N. Tsitsiklis, On the predictability of coupled automata: An allegory about chaos. Complex Syst. 5, 525\u2013539 (1991).","journal-title":"Complex Syst."},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.64.2354"},{"key":"e_1_3_4_34_2","volume-title":"Theory and Applications of Cellular Automata","author":"Wolfram S.","year":"1986","unstructured":"S. Wolfram, Theory and Applications of Cellular Automata (World Scientific Publishers, Singapore, 1986)."},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA7163"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78911-6"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1927.0118"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1421551111"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1162\/99608f92.a11bf693"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1918529117"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.abg8663"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-020-0791-2"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2009-00344-7"},{"key":"e_1_3_4_45_2","unstructured":"N. Peyrard R. Sabbadin \u201cEvaluation of the expected size of a SIR epidemics on a graph\u201d (Tech. Rep. RR-2012-1 Institut National de la Researche Agronomique Unit\u00e9 de Biom\u00e9trie et Intelligence Artificiale Toulouse France 2012)."},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.mbs.2012.07.002"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1186\/s12879-017-2365-1"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.006"},{"key":"e_1_3_4_49_2","doi-asserted-by":"crossref","unstructured":"S. Arora Y. Rabani U. Vazirani \u201cSimulating quadratic dynamical systems is PSPACE-complete\u201d in STOC\u201994: Proceedings of the 26th Annual ACM Symposium on Theory of Computing F. T. Leighton M. T. Goodrich Eds. (Association for Computing Machinery New York 1994) pp. 459\u2013467.","DOI":"10.1145\/195058.195231"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797321602"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651330"},{"key":"e_1_3_4_54_2","unstructured":"P. Sambaturu B. Adhikari B. A. Prakash S. Venkatramanan A. Vullikanti \u201cDesigning effective and practical interventions to contain epidemics\u201d in Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems AAMAS \u201920 A. E. F. Seghrouchni G. Sukthankar B. An N. Yorke-Smith Eds. (International Foundation for Autonomous Agents and Multiagent Systems Liverpool United Kingdom 2020) pp. 1187\u20131195."},{"key":"e_1_3_4_55_2","doi-asserted-by":"crossref","unstructured":"S. Saha A. Adiga B. A. Prakash A. K. S. Vullikanti \u201cApproximation algorithms for reducing the spectral radius to control epidemic spread\u201d in Proceedings of the 2015 SIAM International Conference on Data Mining S. Venkatasubramanian J. Ye Eds. (Society for Industrial and Applied Mathematics Philadelphia 2015) pp. 568\u2013576.","DOI":"10.1137\/1.9781611974010.64"},{"key":"e_1_3_4_56_2","first-page":"041056","article-title":"Phase transition in the recoverability of network history","volume":"9","author":"Young J. G.","year":"2019","unstructured":"J. G. Young ., Phase transition in the recoverability of network history. Phys. Rev. X 9, 041056 (2019).","journal-title":"Phys. Rev. X"},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.109.068702"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-021-01187-2"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.98.052313"},{"key":"e_1_3_4_60_2","doi-asserted-by":"publisher","DOI":"10.1038\/d41586-018-05798-3"},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.016101"},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.92.022821"},{"key":"e_1_3_4_63_2","doi-asserted-by":"crossref","unstructured":"C. Milling C. Caramanis S. Mannor S. Shakkottai \u201cOn identifying the causative network of an epidemic\u201d in 50th Annual Allerton Conference on Communication Control and Computing T. Basar B. Hajek Eds. (IEEE Piscataway NJ 2012) pp. 909\u2013914.","DOI":"10.1109\/Allerton.2012.6483315"},{"key":"e_1_3_4_64_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.112.118701"},{"key":"e_1_3_4_65_2","unstructured":"J. Perl \u201cReverend Bayes on inference engines: A distributed hierarchical approach\u201d in AAAI\u201982: Proceedings of the Second AAAI Conference on Artificial Intelligence D. W. Waltz Ed. (AAAI Press Palo Alto CA 1982) pp. 133\u2013136."},{"key":"e_1_3_4_66_2","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"Gonzalez T.","year":"2018","unstructured":"T. Gonzalez, Handbook of Approximation Algorithms and Metaheuristics (Chapman and Hall\/CRC, Boca Raton, FL, 2018)."},{"key":"e_1_3_4_67_2","doi-asserted-by":"crossref","unstructured":"D. Shah T. Zaman \u201cDetecting sources of computer viruses in networks: Theory and experiment in SIGMETRICS 2010 \u201d Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems V. Misra P. Barford M. S. Squillante Eds. (Association for Computing Machinery New York 2010) pp. 203\u2013214.","DOI":"10.1145\/1811039.1811063"},{"key":"e_1_3_4_68_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2018.0624"},{"key":"e_1_3_4_69_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.90.012801"},{"key":"e_1_3_4_70_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2020.3039494"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.pnas.org\/syndication\/doi\/10.1073\/pnas.2109228119","content-type":"unspecified","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.2109228119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T12:43:37Z","timestamp":1649853817000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.2109228119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,19]]},"references-count":70,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,1,25]]}},"alternative-id":["10.1073\/pnas.2109228119"],"URL":"https:\/\/doi.org\/10.1073\/pnas.2109228119","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,19]]},"assertion":[{"value":"2021-05-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e2109228119"}}