{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T03:33:43Z","timestamp":1773027223243,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1149257, CCF-1423100, DGE-16-44869"],"award-info":[{"award-number":["CCF-1149257, CCF-1423100, DGE-16-44869"]}],"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":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055461","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"523-536","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness"],"prefix":"10.1145","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Columbia University, USA"}]},{"given":"Erik","family":"Waingarten","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}]},{"given":"Jinyu","family":"Xie","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v31:3"},{"key":"e_1_3_2_1_2_1","unstructured":"Roksana Baleshzar Deeparnab Chakrabarty Ramesh Krishnan S. Pallavoor Sofya Raskhodnikova and C. Seshadhri. 2017.  Roksana Baleshzar Deeparnab Chakrabarty Ramesh Krishnan S. Pallavoor Sofya Raskhodnikova and C. Seshadhri. 2017."},{"key":"e_1_3_2_1_3_1","volume-title":"Adaptivity Helps. arXiv preprint:1703.05199","author":"Real-Valued Functions Optimal Unateness","year":"2017","unstructured":"Optimal Unateness Testers for Real-Valued Functions : Adaptivity Helps. arXiv preprint:1703.05199 ( 2017 ). Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. arXiv preprint:1703.05199 (2017)."},{"key":"e_1_3_2_1_4_1","volume-title":"Testing unateness of real-valued functions. arXiv preprint:1608.07652","author":"Baleshzar Roksana","year":"2016","unstructured":"Roksana Baleshzar , Meiram Murzabulatov , Ramesh Krishnan S. Pallavoor , and Sofya Raskhodnikova . 2016. Testing unateness of real-valued functions. arXiv preprint:1608.07652 ( 2016 ). Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, and Sofya Raskhodnikova. 2016. Testing unateness of real-valued functions. arXiv preprint:1608.07652 (2016)."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007414"},{"key":"e_1_3_2_1_6_1","unstructured":"Aleksandrs Belovs and Eric Blais. 2016.  Aleksandrs Belovs and Eric Blais. 2016."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897567"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a016"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.38"},{"key":"e_1_3_2_1_11_1","unstructured":"Jop Bri\u00ebt Sourav Chakraborty David Garc\u00eda-Soriano and Arie Matsliah. 2012.  Jop Bri\u00ebt Sourav Chakraborty David Garc\u00eda-Soriano and Arie Matsliah. 2012."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2765-1"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/13092770X"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488661"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a017"},{"key":"e_1_3_2_1_16_1","unstructured":"Deeparnab Chakrabarty and C. Seshadhri. 2016. A O (n) non-adaptive tester for unateness. arXiv preprint:1608.06980 (2016).  Deeparnab Chakrabarty and C. Seshadhri. 2016. A O (n) non-adaptive tester for unateness. arXiv preprint:1608.06980 (2016)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746570"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.38"},{"key":"e_1_3_2_1_19_1","volume-title":"Beyond Talagrand functions: New lower bounds for testing monotonicity and unateness. arXiv preprint:1702.06997","author":"Chen Xi","year":"2017","unstructured":"Xi Chen , Erik Waingarten , and Jinyu Xie . 2017. Beyond Talagrand functions: New lower bounds for testing monotonicity and unateness. arXiv preprint:1702.06997 ( 2017 ). Xi Chen, Erik Waingarten, and Jinyu Xie. 2017. Beyond Talagrand functions: New lower bounds for testing monotonicity and unateness. arXiv preprint:1702.06997 (2017)."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Yevgeniy Dodis Oded Goldreich Eric Lehman Sofya Raskhodnikova Dana Ron and Alex Samorodnitsky. 1999. Improved testing algorithms for monotonocity. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques.   Yevgeniy Dodis Oded Goldreich Eric Lehman Sofya Raskhodnikova Dana Ron and Alex Samorodnitsky. 1999. Improved testing algorithms for monotonocity. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques.","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_3_2_1_24_1","unstructured":"Oded Goldreich (Ed.). 2010.  Oded Goldreich (Ed.). 2010."},{"key":"e_1_3_2_1_25_1","volume-title":"Current Research and Surveys","author":"Testing Property","unstructured":"Property Testing : Current Research and Surveys . Vol. 6390 . Springer-Verlag Berlin Heidelberg . Property Testing: Current Research and Surveys. Vol. 6390. Springer-Verlag Berlin Heidelberg."},{"key":"e_1_3_2_1_26_1","volume-title":"Testing Monotonicity. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u20191998)","author":"Goldreich Oded","year":"1998","unstructured":"Oded Goldreich , Shafi Goldwasser , Eric Lehman , and Dana Ron . 1998 . Testing Monotonicity. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u20191998) . 426\u2013435. Oded Goldreich, Shafi Goldwasser, Eric Lehman, and Dana Ron. 1998. Testing Monotonicity. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u20191998). 426\u2013435."},{"key":"e_1_3_2_1_27_1","unstructured":"Oded Goldreich Shafi Goldwasser Eric Lehman Dana Ron and Alex Samordinsky. 2000.  Oded Goldreich Shafi Goldwasser Eric Lehman Dana Ron and Alex Samordinsky. 2000."},{"key":"e_1_3_2_1_28_1","volume-title":"301\u2013 337","author":"Monotonicity Testing","year":"2000","unstructured":"Testing Monotonicity . Combinatorica 20, 3 ( 2000 ), 301\u2013 337 . Testing Monotonicity. Combinatorica 20, 3 (2000), 301\u2013 337."},{"key":"e_1_3_2_1_29_1","unstructured":"Shirley Halevy and Eyal Kushilevitz. 2008.  Shirley Halevy and Eyal Kushilevitz. 2008."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v33:1"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.13"},{"key":"e_1_3_2_1_32_1","unstructured":"Subhash Khot and Igor Shinkar. 2016.  Subhash Khot and Igor Shinkar. 2016."},{"key":"e_1_3_2_1_33_1","unstructured":"An O (n) queries adaptive tester for unateness. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques. 37:1\u201337:7.  An O (n) queries adaptive tester for unateness. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques. 37:1\u201337:7."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10097"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000004"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000029"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382559.2382562"},{"key":"e_1_3_2_1_38_1","volume-title":"Servedio","author":"Rubinfeld Ronitt","year":"2009","unstructured":"Ronitt Rubinfeld and Rocco A . Servedio . 2009 . Ronitt Rubinfeld and Rocco A. Servedio. 2009."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v34:1"}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055461","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055461","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":39,"alternative-id":["10.1145\/3055399.3055461","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055461","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}