{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:53:52Z","timestamp":1787500432993,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006063","name":"Paul and Daisy Soros Fellowships for New Americans","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006063","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1453261, CCF-1565235"],"award-info":[{"award-number":["CCF-1453261, CCF-1565235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451078","type":"proceedings-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:26:13Z","timestamp":1623792373000},"page":"490-503","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Algorithmic foundations for the diffraction limit"],"prefix":"10.1145","author":[{"given":"Sitan","family":"Chen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ankur","family":"Moitra","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Beitr\u00e4ge zur Theorie des Mikroskops und der mikroskopischen Wahrnehmung. Archiv f\u00fcr mikroskopische Anatomie, 9, 1","author":"Abbe Ernst","year":"1873","unstructured":"Ernst Abbe. 1873. Beitr\u00e4ge zur Theorie des Mikroskops und der mikroskopischen Wahrnehmung. Archiv f\u00fcr mikroskopische Anatomie, 9, 1, 1873. Pages 413\u2013418."},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the Eighteenth Annual Conference on Learning Theory (COLT). Pages 458\u2013469","author":"Achlioptas D.","unstructured":"D. Achlioptas and F. McSherry. 2005. On Spectral Learning of Mixtures of Distributions. In Proceedings of the Eighteenth Annual Conference on Learning Theory (COLT). Pages 458\u2013469."},{"key":"e_1_3_2_1_3_1","first-page":"1835","article-title":"On the diffraction of an object-glass with circular aperture","volume":"5","author":"Airy George Biddell","year":"1835","unstructured":"George Biddell Airy. 1835. On the diffraction of an object-glass with circular aperture. Transactions of the Cambridge Philosophical Society, 5, 1835. Pages 283.","journal-title":"Transactions of the Cambridge Philosophical Society"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 33rd Symposium on Theory of Computing. Pages 247\u2013257","author":"Arora S.","unstructured":"S. Arora and R. Kannan. 2001. Learning mixtures of arbitrary Gaussians. In Proceedings of the 33rd Symposium on Theory of Computing. Pages 247\u2013257."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/13090818X"},{"key":"e_1_3_2_1_6_1","volume-title":"Building Bridges","author":"Charles Brubaker S","unstructured":"S Charles Brubaker and Santosh S Vempala. 2008. Isotropic PCA and affine-invariant clustering. In Building Bridges. Springer. Pages 241\u2013281."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786443708561813"},{"key":"e_1_3_2_1_8_1","first-page":"6","article-title":"Super-resolution from noisy data","volume":"19","author":"Carlos Fernandez-Granda Emmanuel J","year":"2013","unstructured":"Emmanuel J Cand\\`es and Carlos Fernandez-Granda. 2013. Super-resolution from noisy data. Journal of Fourier Analysis and Applications, 19, 6, 2013. Pages 1229\u20131254.","journal-title":"Journal of Fourier Analysis and Applications"},{"key":"e_1_3_2_1_9_1","volume-title":"es and Carlos Fernandez-Granda","author":"Emmanuel J","year":"2014","unstructured":"Emmanuel J Cand\\`es and Carlos Fernandez-Granda. 2014. Towards a mathematical theory of super-resolution. Communications on pure and applied Mathematics, 67, 6, 2014. Pages 906\u2013956."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1515\/crelle-2014-0078"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814639"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence. Pages 143\u2013151","author":"Dasgupta S.","unstructured":"S. Dasgupta and L. Schulman. 2000. A two-round variant of EM for Gaussian mixtures. In Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence. Pages 143\u2013151."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188758"},{"key":"e_1_3_2_1_14_1","series-title":"SIAM journal on mathematical analysis, 23, 5","volume-title":"Superresolution via sparsity constraints","author":"Donoho David L","year":"1992","unstructured":"David L Donoho. 1992. Superresolution via sparsity constraints. SIAM journal on mathematical analysis, 23, 5, 1992. Pages 1309\u20131331."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0149053"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1364\/JOSA.57.000987"},{"key":"e_1_3_2_1_17_1","volume-title":"Support detection in super-resolution. arXiv preprint arXiv:1302.3921","author":"Fernandez-Granda Carlos","year":"2013","unstructured":"Carlos Fernandez-Granda. 2013. Support detection in super-resolution. arXiv preprint arXiv:1302.3921, 2013."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iaw005"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746616"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509933"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2014.2329131"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Anna C Gilbert Shan Muthukrishnan and Martin Strauss. 2005. Improved time bounds for near-optimal sparse Fourier representations. In Wavelets XI. 5914 Pages 59141A.","DOI":"10.1117\/12.615931"},{"key":"e_1_3_2_1_23_1","first-page":"5","article-title":"A note on band-limited minorants of an Euclidean ball","volume":"146","author":"Felipe","year":"2018","unstructured":"Felipe Gon\\c calves. 2018. A note on band-limited minorants of an Euclidean ball. Proc. Amer. Math. Soc., 146, 5, 2018. Pages 2063\u20132068.","journal-title":"Proc. Amer. Math. Soc."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746579"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214029"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-96-08309-X"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.29.478"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422439"},{"key":"e_1_3_2_1_30_1","unstructured":"Qingqing Huang and Sham M Kakade. 2015. Super-resolution off the grid. In Advances in Neural Information Processing Systems. Pages 2665\u20132673."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634110"},{"key":"e_1_3_2_1_32_1","volume-title":"A robust multi-dimensional sparse Fourier transform in the continuous setting. arXiv preprint arXiv:2005.06156","author":"Jin Yaonan","year":"2020","unstructured":"Yaonan Jin, Daogao Liu, and Zhao Song. 2020. A robust multi-dimensional sparse Fourier transform in the continuous setting. arXiv preprint arXiv:2005.06156, 2020."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806765"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897650"},{"key":"e_1_3_2_1_35_1","volume-title":"Fourier series in control theory","author":"Komornik Vilmos","unstructured":"Vilmos Komornik and Paola Loreti. 2005. Fourier series in control theory. Springer Science & Business Media."},{"key":"e_1_3_2_1_36_1","volume-title":"Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581","author":"Kothari Pravesh K","year":"2017","unstructured":"Pravesh K Kothari and David Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581, 2017."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2015.10.023"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2015.2463255"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746561"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1016552"},{"key":"e_1_3_2_1_42_1","first-page":"49","article-title":"Investigations in optics, with special reference to the spectroscope","volume":"8","author":"Rayleigh Lord","year":"1879","unstructured":"Lord Rayleigh. 1879. Investigations in optics, with special reference to the spectroscope. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 8, 49, 1879. Pages 261\u2013274.","journal-title":"The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.17"},{"key":"e_1_3_2_1_44_1","unstructured":"Arthur Schuster. 1904. An introduction to the theory of optics. E. Arnold."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1086\/142271"},{"key":"e_1_3_2_1_46_1","volume-title":"Parikshit Shah, and Benjamin Recht.","author":"Tang Gongguo","year":"2013","unstructured":"Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht. 2013. Compressed sensing off the grid. IEEE transactions on information theory, 59, 11, 2013. Pages 7465\u20137490."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1985-15349-2"},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of the 43rd Annual Symposium on Foundations of Computer Science. Pages 113\u2013122","author":"Vempala S.","unstructured":"S. Vempala and G. Wang. 2002. A Spectral Algorithm for learning mixtures of distributions. In Proceedings of the 43rd Annual Symposium on Foundations of Computer Science. Pages 113\u2013122."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451078","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451078","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:24:53Z","timestamp":1750181093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451078"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":48,"alternative-id":["10.1145\/3406325.3451078","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451078","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}