{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:22:54Z","timestamp":1772083374240,"version":"3.50.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T00:00:00Z","timestamp":1489104000000},"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":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>The primary problem in property testing is to decide whether a given function satisfies a certain property or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the<jats:italic>uniform<\/jats:italic>distribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions.<\/jats:p><jats:p>In this article, we provide simple and optimal testers for<jats:italic>bounded derivative properties<\/jats:italic>over<jats:italic>arbitrary product distributions<\/jats:italic>. Bounded derivative properties include fundamental properties, such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing over arbitrary ranges.<\/jats:p><jats:p>We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show that this sum-of-depths is also a lower bound. A technical contribution of our work is an<jats:italic>optimal dimension reduction theorem<\/jats:italic>for all bounded derivative properties that relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity, and our theorem is an exponential improvement to the previous best-known result.<\/jats:p>","DOI":"10.1145\/3039241","type":"journal-article","created":{"date-parts":[[2017,3,13]],"date-time":"2017-03-13T12:25:15Z","timestamp":1489407915000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Property Testing on Product Distributions"],"prefix":"10.1145","volume":"13","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[{"name":"Microsoft Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kashyap","family":"Dixit","sequence":"additional","affiliation":[{"name":"Pennsylvania State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhav","family":"Jha","sequence":"additional","affiliation":[{"name":"Zenefits, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.06.001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286500.1286503"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Workshop on Randomization and Computation (RANDOM\u201912)","author":"Awasthi P."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.64"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1055762.1709470"},{"key":"e_1_2_1_6_1","volume-title":"Symposium on Theory of Computing (STOC\u201914)","author":"Berman P."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 18th Annual Symposium on Discrete Algorithms (SODA\u201909)","author":"Bhattacharyya A."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.38"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2765-1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488661"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International Workshop on Randomization and Computation (RANDOM\u201913)","author":"Chakrabarty D."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_24"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM\u201999)","author":"Dodis Y."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a011"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a010"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_22_1","volume-title":"Technical Report TR13-109. Electronic Colloquium on Computational Complexity (ECCC)","author":"Goldreich O.","year":"2013"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"S. Halevy. 2006. Topics in Property Testing. Ph.D. Dissertation. Tel Aviv University Tel Aviv Israel. S. Halevy. 2006. Topics in Property Testing. Ph.D. Dissertation. Tel Aviv University Tel Aviv Israel.","DOI":"10.1179\/033443506788991541"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_28"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645804"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118765.3119096"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1387068.1387072"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.13"},{"key":"e_1_2_1_29_1","unstructured":"D. E. Knuth. 1973. The Art of Computer Programming Vol III: Sorting and Searching. Addison-Wesley New York NY. D. E. Knuth. 1973. The Art of Computer Programming Vol III: Sorting and Searching. Addison-Wesley New York NY."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_45"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3148"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264563"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603055"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039241","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3039241","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:30Z","timestamp":1750217790000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3039241"}},"subtitle":["Optimal Testers for Bounded Derivative Properties"],"short-title":[],"issued":{"date-parts":[[2017,3,10]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3039241"],"URL":"https:\/\/doi.org\/10.1145\/3039241","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,10]]},"assertion":[{"value":"2015-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}