{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T17:27:42Z","timestamp":1790789262698,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF-CAREER","award":["2041920"],"award-info":[{"award-number":["2041920"]}]},{"name":"NSF DMS","award":["2023495"],"award-info":[{"award-number":["2023495"]}]},{"name":"CCF","award":["1740850, 1839317, 1813165, 190838, 19097904"],"award-info":[{"award-number":["1740850, 1839317, 1813165, 190838, 19097904"]}]},{"name":"ARO","award":["W911NF1910294."],"award-info":[{"award-number":["W911NF1910294."]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585167","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"233-241","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an \u00d5(n\u221ad) Monotonicity Tester"],"prefix":"10.1145","author":[{"given":"Hadley","family":"Black","sequence":"first","affiliation":[{"name":"University of California at Los Angeles, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deeparnab","family":"Chakrabarty","sequence":"additional","affiliation":[{"name":"Dartmouth College, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California at Santa Cruz, Santa Cruz, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.06.001"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286500.1286503"},{"key":"e_1_3_2_1_3_1","first-page":"406","article-title":"A Polynomial Lower Bound for Testing Monotonicity","volume":"50","author":"Belovs Aleksandrs","year":"2021","unstructured":"Aleksandrs Belovs and Eric Blais . 2021 . A Polynomial Lower Bound for Testing Monotonicity . SIAM Journal on Computing (SICOMP) , 50 , 3 (2021), 406 \u2013 433 . Prelim. version in Proc., STOC 2016 Aleksandrs Belovs and Eric Blais. 2021. A Polynomial Lower Bound for Testing Monotonicity. SIAM Journal on Computing (SICOMP), 50, 3 (2021), 406\u2013433. Prelim. version in Proc., STOC 2016","journal-title":"SIAM Journal on Computing (SICOMP)"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings, ACM Symposium on Theory of Computing (STOC).","author":"Berman Piotr","year":"2014","unstructured":"Piotr Berman , Sofya Raskhodnikova , and Grigory Yaroslavtsev . 2014 . L_p-testing . In Proceedings, ACM Symposium on Theory of Computing (STOC). Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. 2014. L_p-testing. In Proceedings, ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_5_1","unstructured":"Arnab Bhattacharyya. 2008. A note on the distance to monotonicity of boolean functions. Electronic Colloquium on Computational Complexity (ECCC). \t\t\t\t  Arnab Bhattacharyya. 2008. A note on the distance to monotonicity of boolean functions. Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/100808186"},{"key":"e_1_3_2_1_7_1","unstructured":"Hadley Blach Deeparnab Chakrabarty and C. Seshadhri. 2022. Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an (n\u221a d) Monotonicity Tester. Electronic Colloquium on Computational Complexity (ECCC) 162 (2022) https:\/\/eccc.weizmann.ac.il\/report\/2022\/162\/ \t\t\t\t  Hadley Blach Deeparnab Chakrabarty and C. Seshadhri. 2022. Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an (n\u221a d) Monotonicity Tester. Electronic Colloquium on Computational Complexity (ECCC) 162 (2022) https:\/\/eccc.weizmann.ac.il\/report\/2022\/162\/"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Black Hadley","unstructured":"Hadley Black , Deeparnab Chakrabarty , and C. Seshadhri . 2018. A o(d)\u22c5 (n) Monotonicity Tester for Boolean Functions over the Hypergrid [n]^d . In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA). Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri. 2018. A o(d)\u22c5 (n) Monotonicity Tester for Boolean Functions over the Hypergrid [n]^d. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Black Hadley","unstructured":"Hadley Black , Deeparnab Chakrabarty , and C. Seshadhri . 2020. Domain Reduction: A o(d) Tester for Boolean Functions in d-Dimensions . In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA). Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri. 2020. Domain Reduction: A o(d) Tester for Boolean Functions in d-Dimensions. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_10_1","volume-title":"Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. arXiv, abs\/2011.09441","author":"Black Hadley","year":"2020","unstructured":"Hadley Black , Iden Kalemaj , and Sofya Raskhodnikova . 2020. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. arXiv, abs\/2011.09441 ( 2020 ). Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. 2020. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. arXiv, abs\/2011.09441 (2020)."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.38"},{"key":"e_1_3_2_1_13_1","first-page":"1","article-title":"Improved Monotonicity Testers via Hypercube Embeddings. In Proceedings","volume":"25","author":"Braverman Mark","year":"2023","unstructured":"Mark Braverman , Subhash Khot , Guy Kindler , and Dor Minzer . 2023 . Improved Monotonicity Testers via Hypercube Embeddings. In Proceedings , Innovations in Theoretical Computer Science (ITCS). 25 : 1 \u2013 25 :24. Mark Braverman, Subhash Khot, Guy Kindler, and Dor Minzer. 2023. Improved Monotonicity Testers via Hypercube Embeddings. In Proceedings, Innovations in Theoretical Computer Science (ITCS). 25:1\u201325:24.","journal-title":"Innovations in Theoretical Computer Science (ITCS)."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2765-1"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.21"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3039241"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings, ACM Symposium on Theory of Computing (STOC).","author":"Chakrabarty Deeparnab","unstructured":"Deeparnab Chakrabarty and C. Seshadhri . 2013. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids . In Proceedings, ACM Symposium on Theory of Computing (STOC). Deeparnab Chakrabarty and C. Seshadhri. 2013. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Proceedings, ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/13092770X"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a017"},{"key":"e_1_3_2_1_20_1","first-page":"1","article-title":"Adaptive Boolean Monotonicity Testing in Total Influence Time. In Proceedings","volume":"20","author":"Chakrabarty Deeparnab","year":"2019","unstructured":"Deeparnab Chakrabarty and C. Seshadhri . 2019 . Adaptive Boolean Monotonicity Testing in Total Influence Time. In Proceedings , Innovations in Theoretical Computer Science (ITCS). 20 : 1 \u2013 20 :7. Deeparnab Chakrabarty and C. Seshadhri. 2019. Adaptive Boolean Monotonicity Testing in Total Influence Time. In Proceedings, Innovations in Theoretical Computer Science (ITCS). 20:1\u201320:7.","journal-title":"Innovations in Theoretical Computer Science (ITCS)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746570"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.38"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055461"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"e_1_3_2_1_26_1","article-title":"Approximating the Distance to Monotonicity in High Dimensions","volume":"6","author":"Fattal Shahar","year":"2010","unstructured":"Shahar Fattal and Dana Ron . 2010 . Approximating the Distance to Monotonicity in High Dimensions . ACM Trans. on Algorithms (TALG) , 6 , 3 (2010). Shahar Fattal and Dana Ron. 2010. Approximating the Distance to Monotonicity in High Dimensions. ACM Trans. on Algorithms (TALG), 6, 3 (2010).","journal-title":"ACM Trans. on Algorithms (TALG)"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_26"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1387068.1387072"},{"key":"e_1_3_2_1_32_1","first-page":"1","article-title":"Downsampling for Testing and Learning in Product Distributions. In Proceedings","volume":"229","author":"Harms Nathaniel","year":"2022","unstructured":"Nathaniel Harms and Yuichi Yoshida . 2022 . Downsampling for Testing and Learning in Product Distributions. In Proceedings , International Colloquium on Automata, Languages and Programming (ICALP). 229 , 71: 1 \u2013 71 :19. Nathaniel Harms and Yuichi Yoshida. 2022. Downsampling for Testing and Learning in Product Distributions. In Proceedings, International Colloquium on Automata, Languages and Programming (ICALP). 229, 71:1\u201371:19.","journal-title":"International Colloquium on Automata, Languages and Programming (ICALP)."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1065872"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3148"},{"key":"e_1_3_2_1_35_1","first-page":"101","article-title":"Probabilistic Characteristics of Graphs with Large Connectivity","volume":"10","author":"Margulis Grigory A.","year":"1974","unstructured":"Grigory A. Margulis . 1974 . Probabilistic Characteristics of Graphs with Large Connectivity . Problemy Peredachi Informatsii , 10 , 2 (1974), 101 \u2013 108 . Grigory A. Margulis. 1974. Probabilistic Characteristics of Graphs with Large Connectivity. Problemy Peredachi Informatsii, 10, 2 (1974), 101\u2013108.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_3_2_1_36_1","volume-title":"ITCS 2017","author":"Pallavoor Ramesh Krishnan S.","year":"2018","unstructured":"Ramesh Krishnan S. Pallavoor , Sofya Raskhodnikova , and Nithin Varma . 2018 . Parameterized Property Testing of Functions. ACM Trans. Comput. Theory, 9, 4 (2018), 17:1\u201317:19. Prelim. version in Proc ., ITCS 2017 Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. 2018. Parameterized Property Testing of Functions. ACM Trans. Comput. Theory, 9, 4 (2018), 17:1\u201317:19. Prelim. version in Proc., ITCS 2017"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21029"},{"key":"e_1_3_2_1_38_1","unstructured":"Sofya Raskhodnikova. 1999. Monotonicity Testing. Masters Thesis MIT. \t\t\t\t  Sofya Raskhodnikova. 1999. Monotonicity Testing. Masters Thesis MIT."},{"key":"e_1_3_2_1_39_1","volume-title":"RANDOM 2011","author":"Ron Dana","year":"2012","unstructured":"Dana Ron , Ronitt Rubinfeld , Muli Safra , Alex Samorodnitsky , and Omri Weinstein . 2012 . Approximating the Influence of Monotone Boolean Functions in O(\u221a n) Query Complexity. ACM Trans. Comput. Theory, 4, 4 (2012), 11:1\u201311:12. Prelim. version in Proc ., RANDOM 2011 Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, and Omri Weinstein. 2012. Approximating the Influence of Monotone Boolean Functions in O(\u221a n) Query Complexity. ACM Trans. Comput. Theory, 4, 4 (2012), 11:1\u201311:12. Prelim. version in Proc., RANDOM 2011"},{"key":"e_1_3_2_1_40_1","volume-title":"Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Saks Michael E.","unstructured":"Michael E. Saks and C. Seshadhri . 2008. Parallel monotonicity reconstruction . In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA). Michael E. Saks and C. Seshadhri. 2008. Parallel monotonicity reconstruction. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895691"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585167","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:00Z","timestamp":1750178820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":41,"alternative-id":["10.1145\/3564246.3585167","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585167","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}