{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:26Z","timestamp":1781077646274,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520050","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"832-845","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Kalman filtering with adversarial corruptions"],"prefix":"10.1145","author":[{"given":"Sitan","family":"Chen","sequence":"first","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frederic","family":"Koehler","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ankur","family":"Moitra","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Morris","family":"Yau","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Optimal control: linear quadratic methods","author":"Anderson Brian DO","unstructured":"Brian DO Anderson and John B Moore . 2007. Optimal control: linear quadratic methods . Courier Corporation . Brian DO Anderson and John B Moore. 2007. Optimal control: linear quadratic methods. Courier Corporation."},{"key":"e_1_3_2_1_2_1","volume-title":"Optimal filtering","author":"Anderson Brian DO","unstructured":"Brian DO Anderson and John B Moore . 2012. Optimal filtering . Courier Corporation . Brian DO Anderson and John B Moore. 2012. Optimal filtering. Courier Corporation."},{"key":"e_1_3_2_1_3_1","volume-title":"Vempala","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi , Ilias Diakonikolas , He Jia , Daniel M. Kane , Pravesh K. Kothari , and Santosh S . Vempala . 2020 . Robustly Learning Mixtures of k Arbitrary Gaussians . arxiv:2012.02119. Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala. 2020. Robustly Learning Mixtures of k Arbitrary Gaussians. arxiv:2012.02119."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. arXiv preprint arXiv:2005.02970.  Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. arXiv preprint arXiv:2005.02970.","DOI":"10.1109\/FOCS46700.2020.00023"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451001"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.79"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591886"},{"key":"e_1_3_2_1_8_1","unstructured":"Boaz Barak and David Steurer. 2014. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236.  Boaz Barak and David Steurer. 2014. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055491"},{"key":"e_1_3_2_1_10_1","unstructured":"Sitan Chen Frederic Koehler Ankur Moitra and Morris Yau. 2020. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. arXiv preprint arXiv:2010.04157.  Sitan Chen Frederic Koehler Ankur Moitra and Morris Yau. 2020. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. arXiv preprint arXiv:2010.04157."},{"key":"e_1_3_2_1_11_1","unstructured":"Yeshwanth Cherapanamjeri Efe Aras Nilesh Tripuraneni Michael I Jordan Nicolas Flammarion and Peter L Bartlett. 2020. Optimal Robust Linear Regression in Nearly Linear Time. arXiv preprint arXiv:2007.08137.  Yeshwanth Cherapanamjeri Efe Aras Nilesh Tripuraneni Michael I Jordan Nicolas Flammarion and Peter L Bartlett. 2020. Optimal Robust Linear Regression in Nearly Linear Time. arXiv preprint arXiv:2007.08137."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-EJS1754"},{"key":"e_1_3_2_1_13_1","unstructured":"Arnak Dalalyan and Philip Thompson. 2019. Outlier-robust estimation of a sparse linear model using l1-penalized Huber\u2019s M-estimator. In Advances in Neural Information Processing Systems. 13188\u201313198.  Arnak Dalalyan and Philip Thompson. 2019. Outlier-robust estimation of a sparse linear model using l1-penalized Huber\u2019s M-estimator. In Advances in Neural Information Processing Systems. 13188\u201313198."},{"key":"e_1_3_2_1_14_1","unstructured":"Ilias Diakonikolas Samuel B Hopkins Daniel Kane and Sushrut Karmalkar. 2020. Robustly Learning any Clusterable Mixture of Gaussians. arXiv preprint arXiv:2005.06417.  Ilias Diakonikolas Samuel B Hopkins Daniel Kane and Sushrut Karmalkar. 2020. Robustly Learning any Clusterable Mixture of Gaussians. arXiv preprint arXiv:2005.06417."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305485"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.171"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188758"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-PAS.1975.32044"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_20_1","volume-title":"Positive polynomials in control. 312","author":"Henrion Didier","unstructured":"Didier Henrion and Andrea Garulli . 2005. Positive polynomials in control. 312 , Springer Science & Business Media . Didier Henrion and Andrea Garulli. 2005. Positive polynomials in control. 312, Springer Science & Business Media."},{"key":"e_1_3_2_1_21_1","volume-title":"STATISTICAL INFERENCE AND THE SUM OF SQUARES METHOD. Ph. D. Dissertation","author":"Hopkins Samuel","unstructured":"Samuel Hopkins . 2018. STATISTICAL INFERENCE AND THE SUM OF SQUARES METHOD. Ph. D. Dissertation . Cornell University . Samuel Hopkins. 2018. STATISTICAL INFERENCE AND THE SUM OF SQUARES METHOD. Ph. D. Dissertation. Cornell University."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703732"},{"key":"e_1_3_2_1_24_1","first-page":"799","article-title":"Robust Regression: Asymptotics, Conjectures and Monte Carlo","author":"Huber Peter J","year":"1973","unstructured":"Peter J Huber . 1973 . Robust Regression: Asymptotics, Conjectures and Monte Carlo . The Annals of Statistics , 799 \u2013 821 . Peter J Huber. 1973. Robust Regression: Asymptotics, Conjectures and Monte Carlo. The Annals of Statistics, 799\u2013821.","journal-title":"The Annals of Statistics"},{"key":"e_1_3_2_1_25_1","unstructured":"T. Kailath A.H. Sayed and B. Hassibi. 2000. Linear Estimation. Prentice Hall. isbn:9780130224644 lccn:99047033 https:\/\/books.google.com\/books?id=zNJFAQAAIAAJ  T. Kailath A.H. Sayed and B. Hassibi. 2000. Linear Estimation. Prentice Hall. isbn:9780130224644 lccn:99047033 https:\/\/books.google.com\/books?id=zNJFAQAAIAAJ"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1959.1104873"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.3658902"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2514\/1.G000799"},{"key":"e_1_3_2_1_29_1","volume-title":"Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory. 1420\u20131430","author":"Klivans Adam","year":"2018","unstructured":"Adam Klivans , Pravesh K Kothari , and Raghu Meka . 2018 . Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory. 1420\u20131430 . Adam Klivans, Pravesh K Kothari, and Raghu Meka. 2018. Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory. 1420\u20131430."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.76"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0279-7_18"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451084"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2010.936020"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-017-0784-y"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2008.4739119"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TAC.2011.2166309","article-title":"Kalman filtering with intermittent observations: Tail distribution and critical value","volume":"57","author":"Mo Yilin","year":"2011","unstructured":"Yilin Mo and Bruno Sinopoli . 2011 . Kalman filtering with intermittent observations: Tail distribution and critical value . IEEE Trans. Automat. Control , 57 , 3 (2011), 677 \u2013 689 . Yilin Mo and Bruno Sinopoli. 2011. Kalman filtering with intermittent observations: Tail distribution and critical value. IEEE Trans. Automat. Control, 57, 3 (2011), 677\u2013689.","journal-title":"IEEE Trans. Automat. Control"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0005-1098(72)90044-1"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3216-0_17"},{"key":"e_1_3_2_1_40_1","volume-title":"Analysis of boolean functions","author":"O\u2019Donnell Ryan","unstructured":"Ryan O\u2019Donnell . 2014. Analysis of boolean functions . Cambridge University Press . Ryan O\u2019Donnell. 2014. Analysis of boolean functions. Cambridge University Press."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.111"},{"key":"e_1_3_2_1_42_1","volume-title":"Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph. D. Dissertation","author":"Parrilo Pablo A","unstructured":"Pablo A Parrilo . 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph. D. Dissertation . California Institute of Technology . Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph. D. Dissertation. California Institute of Technology."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1980.1102349"},{"key":"e_1_3_2_1_44_1","volume-title":"Positive polynomials in control","author":"Prajna Stephen","unstructured":"Stephen Prajna , Antonis Papachristodoulou , Peter Seiler , and Pablo A Parrilo . 2005. SOSTOOLS and its control applications . In Positive polynomials in control . Springer , 273\u2013292. Stephen Prajna, Antonis Papachristodoulou, Peter Seiler, and Pablo A Parrilo. 2005. SOSTOOLS and its control applications. In Positive polynomials in control. Springer, 273\u2013292."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2013.6638770"},{"key":"e_1_3_2_1_46_1","volume-title":"Robust recursive estimation of the state of a discrete-time stochastic linear dynamic system in the presence of heavy-tailed observation noise. Ph. D. Dissertation","author":"Schick Irvin C","unstructured":"Irvin C Schick . 1989. Robust recursive estimation of the state of a discrete-time stochastic linear dynamic system in the presence of heavy-tailed observation noise. Ph. D. Dissertation . Massachusetts Institute of Technology . Irvin C Schick. 1989. Robust recursive estimation of the state of a discrete-time stochastic linear dynamic system in the presence of heavy-tailed observation noise. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_47_1","first-page":"1045","article-title":"Robust recursive estimation in the presence of heavy-tailed observation noise","author":"Schick Irvin C","year":"1994","unstructured":"Irvin C Schick and Sanjoy K Mitter . 1994 . Robust recursive estimation in the presence of heavy-tailed observation noise . The Annals of Statistics , 1045 \u2013 1080 . Irvin C Schick and Sanjoy K Mitter. 1994. Robust recursive estimation in the presence of heavy-tailed observation noise. The Annals of Statistics, 1045\u20131080.","journal-title":"The Annals of Statistics"},{"key":"e_1_3_2_1_48_1","first-page":"11","article-title":"Quadratic optimization problems","volume":"25","author":"Shor N.Z.","year":"1987","unstructured":"N.Z. Shor . 1987 . Quadratic optimization problems . Soviet Journal of Computer and Systems Sciences , 25 (1987), 11 . N.Z. Shor. 1987. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 25 (1987), 11.","journal-title":"Soviet Journal of Computer and Systems Sciences"},{"key":"e_1_3_2_1_49_1","volume-title":"Conference On Learning Theory. 439\u2013473","author":"Simchowitz Max","year":"2018","unstructured":"Max Simchowitz , Horia Mania , Stephen Tu , Michael I Jordan , and Benjamin Recht . 2018 . Learning without mixing: Towards a sharp analysis of linear system identification . In Conference On Learning Theory. 439\u2013473 . Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. 2018. Learning without mixing: Towards a sharp analysis of linear system identification. In Conference On Learning Theory. 439\u2013473."},{"key":"e_1_3_2_1_50_1","volume-title":"Conference on Learning Theory. 3320\u20133436","author":"Simchowitz Max","year":"2020","unstructured":"Max Simchowitz , Karan Singh , and Elad Hazan . 2020 . Improper learning for non-stochastic control . In Conference on Learning Theory. 3320\u20133436 . Max Simchowitz, Karan Singh, and Elad Hazan. 2020. Improper learning for non-stochastic control. In Conference on Learning Theory. 3320\u20133436."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2004.834121"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-2789(01)00228-7"},{"key":"e_1_3_2_1_53_1","volume-title":"User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12, 4","author":"Tropp Joel A","year":"2012","unstructured":"Joel A Tropp . 2012. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12, 4 ( 2012 ), 389\u2013434. Joel A Tropp. 2012. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12, 4 (2012), 389\u2013434."},{"key":"e_1_3_2_1_54_1","unstructured":"Anastasios Tsiamis and George Pappas. 2020. Online learning of the kalman filter with logarithmic regret. arXiv preprint arXiv:2002.05141.  Anastasios Tsiamis and George Pappas. 2020. Online learning of the kalman filter with logarithmic regret. arXiv preprint arXiv:2002.05141."},{"key":"e_1_3_2_1_55_1","volume-title":"High-dimensional probability: An introduction with applications in data science. 47","author":"Vershynin Roman","unstructured":"Roman Vershynin . 2018. High-dimensional probability: An introduction with applications in data science. 47 , Cambridge university press . Roman Vershynin. 2018. High-dimensional probability: An introduction with applications in data science. 47, Cambridge university press."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520050","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":55,"alternative-id":["10.1145\/3519935.3520050","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520050","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}