{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005186,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718297","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"1019-1030","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7596-6035","authenticated-orcid":false,"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[{"name":"Dartmouth College, Hanover, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1263-1024","authenticated-orcid":false,"given":"Xi","family":"Chen","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9265-5407","authenticated-orcid":false,"given":"Simeon","family":"Ristic","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2163-3555","authenticated-orcid":false,"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California at Santa Cruz, Santa Cruz, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0097-7981","authenticated-orcid":false,"given":"Erik","family":"Waingarten","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"[n. d.]. Normal distribution. https:\/\/en.wikipedia.org\/wiki\/Normal_distribution."},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NeurIPS ' 2018 ).","author":"Acharya Jayadev","year":"2018","unstructured":"Jayadev Acharya, Arnab Bhattacharyya, Constantinos Daskalakis, and Saravanan Kandasamy. 2018. Learning and testing causal models with interventions. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS ' 2018 )."},{"key":"e_1_3_2_1_3_1","unstructured":"Jayadev Acharya Cl\u00e9ment L. Canonne and Gautam Kamath. 2015. A chasm between identity and equivalence testing with conditional queries. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques."},{"key":"e_1_3_2_1_4_1","unstructured":"Jayadev Acharya Constantinos Daskalakis and Gautam Kamath. 2015. Optimal testing for properties of distributions. Advances in Neural Information Processing Systems 28 ( 2015 )."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.6"},{"key":"e_1_3_2_1_6_1","unstructured":"Tomer Adar Eldar Fischer and Amit Levi. 2024. Improved Bounds for HighDimensional Equivalence and Product Testing using Subcube Queries. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2024 )."},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the 32nd Annual Conference on Learning Theory (COLT ' 2019 ). 34-82","author":"Aliakbarpour Maryam","year":"2019","unstructured":"Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee. 2019. Towards Testing Monotonicity of Distributions Over General Posets. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT ' 2019 ). 34-82."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403645"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892113"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007414"},{"key":"e_1_3_2_1_11_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.-testing. In Proceedings, ACM Symposium on Theory of Computing (STOC)."},{"key":"e_1_3_2_1_12_1","article-title":"Lower Bounds for Testing Graphical Models: Colorings and Antiferromagnetic Ising Models","volume":"21","author":"Bez\u00e1kov\u00e1 Ivona","year":"2020","unstructured":"Ivona Bez\u00e1kov\u00e1, Antonio Blanca, Zongchen Chen, Daniel \u0160tefankovi\u010d, and Eric Vigoda. 2020. Lower Bounds for Testing Graphical Models: Colorings and Antiferromagnetic Ising Models. Journal of Machine Learning Research 21, 25 ( 2020 ), 1-62.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS ' 2011 ).","author":"Bhattacharyya Arnab","year":"2011","unstructured":"Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant. 2011. Testing monotonicityof distributions over general partial orders. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS ' 2011 )."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241377"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i8.28632"},{"volume-title":"Proceedings of the 55th ACM Symposium on the Theory of Computing (STOC ' 2023 ).","author":"Black Hadley","key":"e_1_3_2_1_16_1","unstructured":"Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri. 2023. Directed isoperi\u221a metric theorems for boolean functions on the hypergrid and an e ( ) monotonicity tester. In Proceedings of the 55th ACM Symposium on the Theory of Computing (STOC ' 2023 )."},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the 50th International Colloquium on Automata, Languages and Programming (ICALP ' 2023 ).","author":"Black Hadley","year":"2023","unstructured":"Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. 2023. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. In Proceedings of the 50th International Colloquium on Automata, Languages and Programming (ICALP ' 2023 )."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585212"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the 36th Annual Conference on Learning Theory (COLT ' 2023 ).","author":"Blanca Antonio","year":"2023","unstructured":"Antonio Blanca, Zongchen Chen, Daniel \u0160tefankovi\u010d, and Eric Vigoda. 2023. Complexity of high-dimensional identity testing with coordinate conditional sampling. In Proceedings of the 36th Annual Conference on Learning Theory (COLT ' 2023 )."},{"volume-title":"Topics and Techniques in Distribution Testing: A Biased but Representative Sample","author":"Canonne Cl\u00e9ment L.","key":"e_1_3_2_1_20_1","unstructured":"Cl\u00e9ment L. Canonne. 2022. Topics and Techniques in Distribution Testing: A Biased but Representative Sample. Vol. 19. Foundations and Trends in Communications and Information Theory."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.21"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Cl\u00e9ment L. Canonne Ilias Diakonikolas Themis Gouleakis and Ronitt Rubinfeld. 2018. Testing shape restrictions of discrete distributions. Theory of Computing Systems 62 1 ( 2018 ) 4-62.","DOI":"10.1007\/s00224-017-9785-6"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the 30th Annual Conference on Learning Theory (COLT ' 2017 ).","author":"Canonne Cl\u00e9ment L.","year":"2017","unstructured":"Cl\u00e9ment L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2017. Testing bayesian networks. In Proceedings of the 30th Annual Conference on Learning Theory (COLT ' 2017 )."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945508"},{"volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP ' 2014 ). 283-295","author":"Cl\u00e9ment","key":"e_1_3_2_1_25_1","unstructured":"Cl\u00e9ment L. Canonne and Ronitt Rubinfeld. 2014. Testing probability distributions underlying aggregated data. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP ' 2014 ). 283-295."},{"key":"e_1_3_2_1_26_1","article-title":"An () monotonicity tester for Boolean functions over the hypercube","volume":"45","author":"Chakrabarty Deeparnab","year":"2014","unstructured":"Deeparnab Chakrabarty and C. Seshadhri. 2014. An () monotonicity tester for Boolean functions over the hypercube. SIAM Journal on Computing (SICOMP) 45, 2 ( 2014 ), 461-472.","journal-title":"SIAM Journal on Computing (SICOMP)"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 27rd International Conference on Artificial Intelligence and Statistics (AISTATS ' 2024 ).","author":"Chakraborty Diptarka","year":"2024","unstructured":"Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kuman, and Kuldeep Meel. 2024. Equivalence testing: the power of bounded adaptivity. In Proceedings of the 27rd International Conference on Artificial Intelligence and Statistics (AISTATS ' 2024 )."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.153"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/140964199"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the 34th Annual Conference on Learning Theory (COLT ' 2021 ).","author":"Chen Xi","year":"2021","unstructured":"Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. 2021. Learning and testing junta distributions with sub cube conditioning. In Proceedings of the 34th Annual Conference on Learning Theory (COLT ' 2021 )."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.152"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2932255"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the 30th Annual Conference on Learning Theory (COLT ' 2017 ). 697-703","author":"Daskalakis Constantinos","year":"2017","unstructured":"Constantinos Daskalakis and Qinxuan Pan. 2017. Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing. In Proceedings of the 30th Annual Conference on Learning Theory (COLT ' 2017 ). 697-703."},{"volume-title":"Proceedings of the 56th ACM Symposium on the Theory of Computing (STOC ' 2024 ).","author":"De Anindya","key":"e_1_3_2_1_34_1","unstructured":"Anindya De, Huan Li, Shivam Nadimpalli, and Rocco A. Servedio. 2024. Detecting Low-Degree Truncation. In Proceedings of the 56th ACM Symposium on the Theory of Computing (STOC ' 2024 )."},{"key":"e_1_3_2_1_35_1","volume-title":"Servedio","author":"De Anindya","year":"2023","unstructured":"Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. 2023. Testing convex truncation. In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA ' 2023 )."},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the 32nd Annual Conference on Learning Theory (COLT ' 2019 ).","author":"Diakonikolas Ilias","year":"2019","unstructured":"Ilias Diakonikolas, Daniel M. Kane, and John Peebles. 2019. Testing Identity of Multidimensional Histograms. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT ' 2019 )."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977585.ch31"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 28th Annual Conference on Learning Theory (COLT ' 2015 ).","author":"Falahatgar Moein","year":"2015","unstructured":"Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapathi, and Ananda Theertha Suresh. 2015. Faster algorithms for testing under conditional sampling. In Proceedings of the 28th Annual Conference on Learning Theory (COLT ' 2015 )."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Reza Gheissari Eyal Lubetzky and Yuval Peres. 2018. Concentration inequalities for polynomials of contracting Ising models. Electronic Communications in Probability 23 ( 2018 ).","DOI":"10.1214\/18-ECP173"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Oded Goldreich Shafi Goldwasser Eric Lehman Dana Ron and Alex Samordinsky. 2000. Testing Monotonicity. Combinatorica 20 3 ( 2000 ) 301-337.","DOI":"10.1007\/s004930070011"},{"key":"e_1_3_2_1_41_1","unstructured":"Oded Goldreich and Dana Ron. 2000. On testing expansion in bounded degree graphs. ECCC preprint: TR00-020 ( 2000 )."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.43"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1065872"},{"key":"e_1_3_2_1_44_1","volume-title":"Proceedings of the 36th Annual Conference on Learning Theory (COLT ' 2023 ).","author":"Mahajan Gaurav","year":"2023","unstructured":"Gaurav Mahajan, Sham Kakade, Akshay Krishnamurthy, and Cyril Zhang. 2023. Learning Hidden Markov Models Using Conditional Samples. In Proceedings of the 36th Annual Conference on Learning Theory (COLT ' 2023 )."},{"key":"e_1_3_2_1_45_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems 33 ( NeurIPS ' 2020 ).","author":"Meel Kuldeep S.","year":"2020","unstructured":"Kuldeep S. Meel, Yash Pote, and Sourav Chakraborty. 2020. On testing of samplers. In Proceedings of Advances in Neural Information Processing Systems 33 ( NeurIPS ' 2020 )."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.23"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS ' 2018 ).","author":"Onak Krzysztof","year":"2018","unstructured":"Krzysztof Onak and Xiaorui Sun. 2018. Probability-revealing samples. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS ' 2018 )."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Ramesh Krishnan S. Pallavoor Sofya Raskhodnikova and Erik Waingarten. 2022. Approximating the distance to monotonicity of Boolean functions. Random Structures Algorithms 60 2 ( 2022 ) 233-260.","DOI":"10.1002\/rsa.21029"},{"key":"e_1_3_2_1_49_1","unstructured":"Renato Ferreira Pinto Jr. 2023. Directed Poincar\u00e9 Inequalities and 1 Monotonicity Testing of Lipschitz Functions. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM ' 2023 )."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00134"},{"volume-title":"Proceedings of Advances in Neural Information Processing Systems 35 ( NeurIPS ' 2022 ).","author":"Pote Yash","key":"e_1_3_2_1_51_1","unstructured":"Yash Pote and Kuldeep S. Meel. 2022. On scalable testing of samplers. In Proceedings of Advances in Neural Information Processing Systems 35 ( NeurIPS ' 2022 )."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/070701649"},{"key":"e_1_3_2_1_53_1","volume-title":"Servedio","author":"Rubinfeld Ronitt","year":"2009","unstructured":"Ronitt Rubinfeld and Rocco A. Servedio. 2009. Testing monotone highdimensional distributions. Random Structures and Algorithms 34, 1 ( 2009 ), 24-44."},{"key":"e_1_3_2_1_54_1","volume-title":"Proceedings of the 2020 ACM Conference on Innovations in Theoretical Computer Science (ITCS ' 2020 ).","author":"Rubinfeld Ronitt","year":"2020","unstructured":"Ronitt Rubinfeld and Arsen Vasilyan. 2020. Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples. In Proceedings of the 2020 ACM Conference on Innovations in Theoretical Computer Science (ITCS ' 2020 )."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Michel Talagrand. 1993. Isoperimetry logarithmic Sobolev inequalities on the discrete cube and Margulis' graph connectivity theorem. Geom. Func. Anal. 3 3 ( 1993 ) 295-314.","DOI":"10.1007\/BF01895691"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734066"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"crossref","unstructured":"Received 2024-11-04; accepted 2025-02-01","DOI":"10.47829\/COS.2024.11201"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:49:35Z","timestamp":1750693775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":57,"alternative-id":["10.1145\/3717823.3718297","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718297","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}