Property Testing on Product Distributions
Deeparnab Chakrabarty, Kashyap Dixit, Madhav Kumar Jha, Comandur Seshadhri · ACM Transactions on Algorithms · 2017
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 theuniformdistribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this article, we provide simple and optimal testers forbounded derivative propertiesoverarbitrary product distributions. 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. 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 anoptimal dimension reduction theoremfor 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.