{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:51Z","timestamp":1781031411105,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF 2045128"],"award-info":[{"award-number":["CCF 2045128"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2211238"],"award-info":[{"award-number":["CCF-2211238"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2106429"],"award-info":[{"award-number":["CCF-2106429"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014037","name":"National Defense Science and Engineering Graduate","doi-asserted-by":"publisher","award":["NDSEG Fellowship"],"award-info":[{"award-number":["NDSEG Fellowship"]}],"id":[{"id":"10.13039\/100014037","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800794","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"799-805","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing Noisy Low-Degree Polynomials for Sparsity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2491-0044","authenticated-orcid":false,"given":"Yiqiao","family":"Bao","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6795-8211","authenticated-orcid":false,"given":"Anindya","family":"De","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1825-6122","authenticated-orcid":false,"given":"Shivam","family":"Nadimpalli","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2407-543X","authenticated-orcid":false,"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-1919-0782","authenticated-orcid":false,"given":"Nathan","family":"White","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proc. RANDOM. 188\u2013199","author":"Alon N.","unstructured":"N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron. 2003. Testing Low-Degree Polynomials over GF(2). In Proc. RANDOM. 188\u2013199."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634111"},{"key":"e_1_3_2_1_3_1","volume-title":"Philips George John, and Sayantan Sen","author":"Arora Vipul","year":"2025","unstructured":"Vipul Arora, Arnab Bhattacharyya, Philips George John, and Sayantan Sen. 2025. Testing Sparse Functions over the Reals. Manuscript at https:\/\/vipularora219.github.io\/"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-020-05868-6"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_26"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_8_1","volume-title":"Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 610\u2013623","author":"Chen Xue","unstructured":"Xue Chen, Anindya De, and Rocco A. Servedio. 2020. Testing noisy linear functions for sparsity. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 610\u2013623."},{"key":"e_1_3_2_1_9_1","first-page":"1","article-title":"Sample-Based High-Dimensional Convexity testing. In Proceedings of the 17th Int","volume":"37","author":"Chen X.","year":"2017","unstructured":"X. Chen, A. Freilich, R. Servedio, and T. Sun. 2017. Sample-Based High-Dimensional Convexity testing. In Proceedings of the 17th Int. Workshop on Randomization and Computation (RANDOM). 37:1\u201337:20.","journal-title":"Workshop on Randomization and Computation (RANDOM)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3213772"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055461"},{"key":"e_1_3_2_1_12_1","volume-title":"Conference on Learning Theory, COLT 2019","volume":"993","author":"De Anindya","year":"2019","unstructured":"Anindya De, Elchanan Mossel, and Joe Neeman. 2019. Is your function low dimensional? In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research, Vol. 99). PMLR, 979\u2013993."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451115"},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. 48th Ann. Symposium on Computer Science (FOCS). 549\u2013558","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio, and A. Wan. 2007. Testing for Concise Representations. In Proc. 48th Ann. Symposium on Computer Science (FOCS). 549\u2013558."},{"key":"e_1_3_2_1_15_1","volume-title":"Proc. 16th International Colloquium on Algorithms, Languages and Programming (ICALP). 502\u2013514","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, H. Lee, K. Matulef, R. Servedio, and A. Wan. 2008. Efficiently Testing Sparse GF(2) Polynomials. In Proc. 16th International Colloquium on Algorithms, Languages and Programming (ICALP). 502\u2013514."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-007-0068-9"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"e_1_3_2_1_19_1","volume-title":"Proc. 34th Annual ACM Symposium on the Theory of Computing. 474\u2013483","author":"Fischer E.","unstructured":"E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky. 2002. Monotonicity Testing Over General Poset Domains. In Proc. 34th Annual ACM Symposium on the Theory of Computing. 474\u2013483."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898355"},{"key":"e_1_3_2_1_22_1","volume-title":"Proc. 36th International Colloquium on Automata, Languages and Programming (ICALP). 500\u2013512","author":"Gopalan P.","unstructured":"P. Gopalan, R. O\u2019Donnell, R. Servedio, A. Shpilka, and K. Wimmer. 2009. Testing Fourier dimensionality and sparsity. In Proc. 36th International Colloquium on Automata, Languages and Programming (ICALP). 500\u2013512."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.07.012"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310479"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1656"},{"key":"e_1_3_2_1_26_1","volume-title":"Sparse polynomial learning and graph sketching. Advances in Neural Information Processing Systems, 27","author":"Kocaoglu Murat","year":"2014","unstructured":"Murat Kocaoglu, Karthikeyan Shanmugam, Alexandros G Dimakis, and Adam Klivans. 2014. Sparse polynomial learning and graph sketching. Advances in Neural Information Processing Systems, 27 (2014)."},{"key":"e_1_3_2_1_27_1","volume-title":"An active learning framework using sparse-graph codes for sparse polynomials and graph sketching. Advances in Neural Information Processing Systems, 28","author":"Li Xiao","year":"2015","unstructured":"Xiao Li and Kannan Ramchandran. 2015. An active learning framework using sparse-graph codes for sparse polynomials and graph sketching. Advances in Neural Information Processing Systems, 28 (2015)."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958029"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21945"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_1_33_1","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"Tarski Alfred","unstructured":"Alfred Tarski. 1948. A Decision Method for Elementary Algebra and Geometry. The RAND Corporation, Santa Monica, CA."}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800794","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:57:02Z","timestamp":1781027822000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800794"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":33,"alternative-id":["10.1145\/3798129.3800794","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800794","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}