{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T19:32:02Z","timestamp":1783971122399,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":46,"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:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2047\/1 ? 390685813"],"award-info":[{"award-number":["EXC-2047\/1 ? 390685813"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","award":["FG-2018-10533"],"award-info":[{"award-number":["FG-2018-10533"]}],"id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["DMS-2031883,DMS-1737944"],"award-info":[{"award-number":["DMS-2031883,DMS-1737944"]}],"id":[{"id":"10.13039\/100000001","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.3451115","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"584-597","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Robust testing of low dimensional functions"],"prefix":"10.1145","author":[{"given":"Anindya","family":"De","sequence":"first","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elchanan","family":"Mossel","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joe","family":"Neeman","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Jimmy Ba and Rich Caruana. 2014. Do deep nets really need to be deep? In Advances in Neural Information Processing Systems. Pages 2654\u20132662."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.64"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_3_2_1_4_1","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"Blais E.","unstructured":"E. Blais. 2008. Improved bounds for testing juntas. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer. Pages 317\u2013330."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536437"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 2113\u20132132","author":"Blais E.","unstructured":"E. Blais, C. Canonne, T. Eden, A. Levi, and D. Ron. 2018. Tolerant junta testing and the connection to submodular optimization and function isomorphism. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 2113\u20132132."},{"key":"e_1_3_2_1_7_1","volume-title":"Relevant examples and relevant features: Thoughts from computational learning theory","author":"Blum A.","year":"1994","unstructured":"A. Blum. 1994. Relevant examples and relevant features: Thoughts from computational learning theory. 1994."},{"key":"e_1_3_2_1_8_1","first-page":"2","article-title":"A polynomial time algorithm for learning noisy linear threshold functions","volume":"22","author":"Blum A.","year":"1997","unstructured":"A. Blum, A. Frieze, R. Kannan, and S. Vempala. 1997. A polynomial time algorithm for learning noisy linear threshold functions. Algorithmica, 22, 1\/2, 1997. Pages 35\u201352.","journal-title":"Algorithmica"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00063-5"},{"key":"e_1_3_2_1_10_1","volume-title":"Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC","author":"Bshouty Nader H","year":"2019","unstructured":"Nader H Bshouty. 2019. Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC 2019)."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150464"},{"key":"e_1_3_2_1_12_1","volume-title":"27th Annual Conference on Computational Complexity (CCC). Pages 148\u2013158","author":"Chakraborty S.","unstructured":"S. Chakraborty, E. Fischer, D. Garc\u00eda-Soriano, and A. Matsliah. 2012. Junto-symmetric functions, hypergraph isomorphism and crunching. In 27th Annual Conference on Computational Complexity (CCC). Pages 148\u2013158."},{"key":"e_1_3_2_1_13_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Chen Xi","year":"2017","unstructured":"Xi Chen, Adam Freilich, Rocco A Servedio, and Timothy Sun. 2017. Sample-Based High-Dimensional Convexity Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2017)."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the ACM STOC","author":"Chen X.","year":"2018","unstructured":"X. Chen, Z. Liu, Rocco A. Servedio, Y. Sheng, and J. Xie. 2018. Distribution free junta testing. In Proceedings of the ACM STOC 2018."},{"key":"e_1_3_2_1_15_1","first-page":"1","article-title":"Settling the Query Complexity of Non-adaptive Junta Testing. In Proceedings of the 32Nd Computational Complexity Conference","volume":"26","author":"Chen Xi","year":"2017","unstructured":"Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. 2017. Settling the Query Complexity of Non-adaptive Junta Testing. In Proceedings of the 32Nd Computational Complexity Conference. Pages 26:1\u201326:19.","journal-title":"Pages"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897520"},{"key":"e_1_3_2_1_17_1","first-page":"993","volume-title":"Conference on Learning Theory, COLT 2019. Proceedings of Machine Learning Research. 99","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. Proceedings of Machine Learning Research. 99, Pages 979\u2013993."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00090"},{"key":"e_1_3_2_1_19_1","unstructured":"Ilias Diakonikolas Themis Gouleakis and Christos Tzamos. 2019. Distribution-independent PAC learning of halfspaces with Massart noise. In Advances in Neural Information Processing Systems. Pages 4749\u20134760."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188754"},{"key":"e_1_3_2_1_21_1","volume-title":"Proc. 48th Ann. Symposium on Computer Science (FOCS). Pages 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). Pages 549\u2013558."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"e_1_3_2_1_23_1","volume-title":"Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS). Pages 543\u2013552","author":"Guruswami V.","unstructured":"V. Guruswami and P. Raghavendra. 2006. Hardness of learning halfspaces with noise. In Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS). Pages 543\u2013552."},{"key":"e_1_3_2_1_24_1","first-page":"1","article-title":"Distribution-Free Connectivity Testing for Sparse Graphs","volume":"51","author":"Halevy S.","year":"2004","unstructured":"S. Halevy and E. Kushilevitz. 2004. Distribution-Free Connectivity Testing for Sparse Graphs. Algorithmica, 51, 1, 2004. Pages 24\u201348.","journal-title":"Algorithmica"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645804"},{"key":"e_1_3_2_1_26_1","first-page":"6","article-title":"An invariance principle for polytopes","volume":"59","author":"Harsha Prahladh","year":"2013","unstructured":"Prahladh Harsha, Adam Klivans, and Raghu Meka. 2013. An invariance principle for polytopes. Journal of the ACM (JACM), 59, 6, 2013. Pages 1\u201325.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_3_2_1_28_1","volume-title":"Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). Pages 541\u2013550","author":"Klivans A.","unstructured":"A. Klivans, R. O'Donnell, and R. Servedio. 2008. Learning Geometric Concepts via Gaussian Surface Area. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). Pages 541\u2013550."},{"key":"e_1_3_2_1_29_1","first-page":"1214","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014","author":"Kothari P.","year":"2014","unstructured":"P. Kothari, A. Nayyeri, R. O'Donnell, and C. Wu. 2014. Testing Surface Area. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014. Pages 1204\u20131214."},{"key":"e_1_3_2_1_30_1","first-page":"1994","article-title":"Semigroup proofs of the isoperimetric inequality in Euclidean and Gauss space","volume":"118","author":"Ledoux M.","year":"1994","unstructured":"M. Ledoux. 1994. Semigroup proofs of the isoperimetric inequality in Euclidean and Gauss space. Bull. Sci. Math., 118, 1994. Pages 485\u2013510.","journal-title":"Bull. Sci. Math."},{"key":"e_1_3_2_1_31_1","first-page":"305","article-title":"The geometry of Markov diffusion generators. In Annales de la Facult\u00e9 des sciences de Toulouse","author":"Ledoux Michel","year":"2000","unstructured":"Michel Ledoux. 2000. The geometry of Markov diffusion generators. In Annales de la Facult\u00e9 des sciences de Toulouse: Math\u00e9matiques. 9, Pages 305\u2013366.","journal-title":"Math\u00e9matiques. 9, Pages"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053606000000786"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/070707890"},{"key":"e_1_3_2_1_34_1","volume-title":"Servedio","author":"Matulef Kevin","year":"2009","unstructured":"Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. 2009. Testing \\pm 1-weight halfspace. In APPROX-RANDOM. Pages 646\u2013657."},{"key":"e_1_3_2_1_35_1","first-page":"1920","article-title":"On the Reciprocal of the General Algebraic","volume":"26","author":"Moore E. H.","year":"1920","unstructured":"E. H. Moore. 1920. On the Reciprocal of the General Algebraic Matrix. Bull. Amer. Math. Soc., 26, 1920. Pages 394\u2013395.","journal-title":"Matrix. Bull. Amer. Math. Soc."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591807"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101407444"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100030401"},{"key":"e_1_3_2_1_40_1","volume-title":"Lecture notes in Math.","author":"Pisier G.","unstructured":"G. Pisier. 1986. Probabilistic methods in the geometry of Banach spaces. In Lecture notes in Math.. Springer. Pages 167\u2013241."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9858-0"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"e_1_3_2_1_43_1","volume-title":"Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences. In 59th IEEE Annual Symposium on Foundations of Computer Science. Pages 967\u2013978","author":"M.","year":"2018","unstructured":"M. Sa\\v glam. 2018. Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences. In 59th IEEE Annual Symposium on Foundations of Computer Science. Pages 967\u2013978."},{"key":"e_1_3_2_1_44_1","volume-title":"Proceedings of CCC. 33","author":"Servedio R.","unstructured":"R. Servedio, L-Y. Tan, and J. Wright. 2015. Adaptivity helps for testing juntas. In Proceedings of CCC. 33,"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2013.6810286"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.19"}],"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.3451115","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451115","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":46,"alternative-id":["10.1145\/3406325.3451115","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451115","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"}}]}}