{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:08Z","timestamp":1750220768662,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384239","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"610-623","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing noisy linear functions for sparsity"],"prefix":"10.1145","author":[{"given":"Xue","family":"Chen","sequence":"first","affiliation":[{"name":"Northwestern University, USA"}]},{"given":"Anindya","family":"De","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1137\/1.9781611973075.95"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1109\/FOCS.2012.64"},{"key":"e_1_3_2_1_3_1","series-title":"Lecture Notes in Statistics, vol 50.","volume-title":"Parametric Statistical Models and Likelihood","author":"Barndorff-Nielsen O.E.","unstructured":"O.E. Barndorff-Nielsen . 1988. Cumulants . In: Parametric Statistical Models and Likelihood . Lecture Notes in Statistics, vol 50. . Springer , New York . isbn:978-0-387-96928-2 O.E. Barndorff-Nielsen. 1988. Cumulants. In: Parametric Statistical Models and Likelihood. Lecture Notes in Statistics, vol 50.. Springer, New York. isbn:978-0-387-96928-2"},{"key":"e_1_3_2_1_4_1","volume-title":"Symposium on Theory of Computing, STOC 2014","author":"Berman Piotr","year":"2014","unstructured":"Piotr Berman , Sofya Raskhodnikova , and Grigory Yaroslavtsev . 2014 . L_ p-testing . In Symposium on Theory of Computing, STOC 2014 , New York, NY, USA, May 31 - June 03, 2014, David B. Shmoys (Ed.). ACM, 164\u2013173. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. 2014. L_ p-testing. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, David B. Shmoys (Ed.). ACM, 164\u2013173."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1137\/1.9781611973105.97"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1002\/rsa.20507"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1145\/1536414.1536437"},{"key":"e_1_3_2_1_8_1","volume-title":"Testing Juntas: A Brief Survey. In Property Testing - Current Research and Surveys. 32\u201340.","author":"Blais E.","year":"2010","unstructured":"E. Blais . 2010 . Testing Juntas: A Brief Survey. In Property Testing - Current Research and Surveys. 32\u201340. E. Blais. 2010. Testing Juntas: A Brief Survey. In Property Testing - Current Research and Surveys. 32\u201340."},{"key":"e_1_3_2_1_9_1","first-page":"24","article-title":"Tolerant junta testing and the connection to submodular optimization and function isomorphism","volume":"11","author":"Blais Eric","year":"2019","unstructured":"Eric Blais , Cl\u00e9ment L Canonne , Talya Eden , Amit Levi , and Dana Ron . 2019 . Tolerant junta testing and the connection to submodular optimization and function isomorphism . ACM Transactions on Computation Theory (TOCT) , 11 , 4 (2019), 24 . Eric Blais, Cl\u00e9ment L Canonne, Talya Eden, Amit Levi, and Dana Ron. 2019. Tolerant junta testing and the connection to submodular optimization and function isomorphism. ACM Transactions on Computation Theory (TOCT), 11, 4 (2019), 24.","journal-title":"ACM Transactions on Computation Theory (TOCT)"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1016\/0022-0000(93)90044-W"},{"unstructured":"Wlodzimierz Bryc. 2005. Normal Distribution: characterizations with applications. isbn:B0006BSUIC https:\/\/homepages.uc.edu\/~brycwz\/probab\/charakt\/charakt.pdf  Wlodzimierz Bryc. 2005. Normal Distribution: characterizations with applications. isbn:B0006BSUIC https:\/\/homepages.uc.edu\/~brycwz\/probab\/charakt\/charakt.pdf","key":"e_1_3_2_1_11_1"},{"unstructured":"W. Bryc. 2019. Personal communication.  W. Bryc. 2019. Personal communication.","key":"e_1_3_2_1_12_1"},{"key":"e_1_3_2_1_13_1","volume-title":"Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC). 2:1\u20132:13","author":"Bshouty Nader H.","year":"2019","unstructured":"Nader H. Bshouty . 2019 . Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC). 2:1\u20132:13 . Nader H. Bshouty. 2019. Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC). 2:1\u20132:13."},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. International Congress of Mathematicians","author":"Candes E.","year":"2006","unstructured":"E. Candes . 2006 . Compressive sampling . In Proc. International Congress of Mathematicians , Madrid, Spain , Aug. 2006. E. Candes. 2006. Compressive sampling. In Proc. International Congress of Mathematicians, Madrid, Spain, Aug. 2006."},{"key":"e_1_3_2_1_15_1","volume-title":"Sparsity and incoherence in compressive sampling. Inverse problems, 23, 3","author":"Candes Emmanuel","year":"2007","unstructured":"Emmanuel Candes and Justin Romberg . 2007. Sparsity and incoherence in compressive sampling. Inverse problems, 23, 3 ( 2007 ), 969. Emmanuel Candes and Justin Romberg. 2007. Sparsity and incoherence in compressive sampling. Inverse problems, 23, 3 (2007), 969."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1016\/j.crma.2008.03.014"},{"key":"e_1_3_2_1_17_1","volume-title":"Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59, 8","author":"Candes Emmanuel J","year":"2006","unstructured":"Emmanuel J Candes , Justin K Romberg , and Terence Tao . 2006. Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59, 8 ( 2006 ), 1207\u20131223. Emmanuel J Candes, Justin K Romberg, and Terence Tao. 2006. Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59, 8 (2006), 1207\u20131223."},{"key":"e_1_3_2_1_18_1","volume-title":"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 APPROX\/RANDOM 2017 . Xi Chen, Adam Freilich, Rocco A Servedio, and Timothy Sun. 2017. Sample-Based High-Dimensional Convexity Testing. In APPROX\/RANDOM 2017."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1016\/j.ipl.2004.01.023"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1016\/j.jcss.2003.11.004"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1016\/j.jcss.2003.11.004"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1016\/j.jcss.2003.11.004"},{"volume-title":"Data analysis using regression and multilevel\/hierarchical models","author":"Gelman Andrew","unstructured":"Andrew Gelman and Jennifer Hill . 2006. Data analysis using regression and multilevel\/hierarchical models . Cambridge University Press . Andrew Gelman and Jennifer Hill. 2006. Data analysis using regression and multilevel\/hierarchical models. Cambridge University Press.","key":"e_1_3_2_1_23_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1145\/103418.103429"},{"volume-title":"Property Testing: Current Research and Surveys","unstructured":"2010. Property Testing: Current Research and Surveys , O. Goldreich (Ed.). Springer . LNCS 6390. 2010. Property Testing: Current Research and Surveys, O. Goldreich (Ed.). Springer. LNCS 6390.","key":"e_1_3_2_1_25_1"},{"volume-title":"Introduction to Property Testing","author":"Goldreich O.","unstructured":"O. Goldreich . 2017. Introduction to Property Testing . Cambridge University Press . O. Goldreich. 2017. Introduction to Property Testing. Cambridge University Press.","key":"e_1_3_2_1_26_1"},{"key":"e_1_3_2_1_27_1","first-page":"7","article-title":"On Sample-Based Testers","volume":"8","author":"Goldreich Oded","year":"2016","unstructured":"Oded Goldreich and Dana Ron . 2016 . On Sample-Based Testers . ACM Transactions on Computation Theory (TOCT) , 8 , 2 (2016), 7 . Oded Goldreich and Dana Ron. 2016. On Sample-Based Testers. ACM Transactions on Computation Theory (TOCT), 8, 2 (2016), 7.","journal-title":"ACM Transactions on Computation Theory (TOCT)"},{"unstructured":"William Greene. 2003. Econometric analysis. Pearson Education.  William Greene. 2003. Econometric analysis. Pearson Education.","key":"e_1_3_2_1_28_1"},{"unstructured":"S. Janson. 2019. Personal communication.  S. Janson. 2019. Personal communication.","key":"e_1_3_2_1_29_1"},{"volume-title":"Proc. 40th Annual ACM Symposium on Theory of Computing (STOC). 403\u2013412","author":"Kaufman T.","unstructured":"T. Kaufman and M. Sudan . 2008. Algebraic property testing: the role of invariance . In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC). 403\u2013412 . T. Kaufman and M. Sudan. 2008. Algebraic property testing: the role of invariance. In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC). 403\u2013412.","key":"e_1_3_2_1_30_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1006\/jcss.1999.1656"},{"unstructured":"Weihao Kong and Gregory Valiant. 2018. Estimating learnability in the sublinear data regime. In Advances in Neural Information Processing Systems. 5455\u20135464.  Weihao Kong and Gregory Valiant. 2018. Estimating learnability in the sublinear data regime. In Advances in Neural Information Processing Systems. 5455\u20135464.","key":"e_1_3_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1007\/BF01210677"},{"unstructured":"Jozef Marcinkiewicz and Antoni Zygmund. 1964. Collected papers. Wydawnictwo Naukowe PWN Poland. isbn:B0006BSUIC  Jozef Marcinkiewicz and Antoni Zygmund. 1964. Collected papers. Wydawnictwo Naukowe PWN Poland. isbn:B0006BSUIC","key":"e_1_3_2_1_34_1"},{"unstructured":"J. Neeman. 2019. Personal communication.  J. Neeman. 2019. Personal communication.","key":"e_1_3_2_1_35_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1016\/j.jcss.2006.03.002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1109\/ISIT.2012.6283954"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1561\/2200000004"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1561\/0400000029"},{"volume-title":"Complex Analysis","author":"Stein Elias","unstructured":"Elias Stein and Rami Shakarchi . 2003. Complex Analysis . Princeton University Press , Princeton, New Jersey. Elias Stein and Rami Shakarchi. 2003. Complex Analysis. Princeton University Press, Princeton, New Jersey.","key":"e_1_3_2_1_40_1"},{"unstructured":"Josh Swanson. 2017. Asymptotic Normality and Combinatorial Statistics. http:\/\/www.math.ucsd.edu\/~jswanson\/talks\/2017_asymptotic_normality.pdf  Josh Swanson. 2017. Asymptotic Normality and Combinatorial Statistics. http:\/\/www.math.ucsd.edu\/~jswanson\/talks\/2017_asymptotic_normality.pdf","key":"e_1_3_2_1_41_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '20","name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384239","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":41,"alternative-id":["10.1145\/3357713.3384239","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384239","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}