More Like this

1. On Optimal Testing of Linearity

   Arora, Vipul; Kelman, Esty; Meir, Uri (January 2025, SIAM Symposium on Simplicity in Algorithms (SOSA))

   Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about Linearity testing in order to resolve two recent versions of this task. First, we focus on the online-manipulation-resilient model introduced by Kalemaj, Raskhodnikova and Varma (Theory of Computing 2023). In this model, up to t data entries are adversarially manipulated after each query is answered. Ben-Eliezer, Kelman, Meir, and Raskhodnikova (ITCS 2024) showed an asymptotically optimal Linearity tester that is resilient to t manipulations per query, but fails if t is too large. We simplify their analysis for the regime of small t, and for larger values of t we instead use sample-based testers, as defined by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A key observation is that sample-based testing is resilient to online manipulations but still achieves optimal query complexity for Linearity when t is large. We complement our result by showing that when t is very large any reasonable property, and in particular Linearity, cannot be tested at all. Second, we consider Linearity over the reals with proximity parameter ε. Fleming and Yoshida (ITCS 2020) gave a tester using O(1/ε · log(1/ε)) queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses O(1/ε) queries. This modification works for the low-degree testers presented in Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 2023) as well, resulting in optimal testers for degree-d polynomials, for any constant d. 

   more » « less
2. On Optimal Testing of Linearity

   Arora, Vipul; Kelman, Esty; Meir, Uri (January 2025, SIAM Symposium on Simplicity in Algorithms)

   Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about Linearity testing in order to resolve two recent versions of this task. First, we focus on the online-manipulation-resilient model introduced by Kalemaj, Raskhodnikova and Varma (Theory of Computing 2023). In this model, up to t data entries are adversarially manipulated after each query is answered. Ben-Eliezer, Kelman, Meir, and Raskhodnikova (ITCS 2024) showed an asymptotically optimal Linearity tester that is resilient to t manipulations per query, but fails if t is too large. We simplify their analysis for the regime of small t, and for larger values of t we instead use sample-based testers, as defined by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A key observation is that sample-based testing is resilient to online manipulations but still achieves optimal query complexity for Linearity when t is large. We complement our result by showing that when t is very large any reasonable property, and in particular Linearity, cannot be tested at all. Second, we consider Linearity over the reals with proximity parameter ε. Fleming and Yoshida (ITCS 2020) gave a tester using O (1/ε · log (1/ε)) queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses O (1/ε) queries. This modification works for the low-degree testers presented in Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 2023) as well, resulting in optimal testers for degree-d polynomials, for any constant d. 

   more » « less
3. Reconstructing decision trees

   Blanc, G.; Lange, J.; Tan, L. (January 2022, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022))

   We give the first reconstruction algorithm for decision trees: given queries to a function f that is opt-close to a size-s decision tree, our algorithm provides query access to a decision tree T where: - T has size S := s^O((log s)²/ε³); - dist(f,T) ≤ O(opt)+ε; - Every query to T is answered with poly((log s)/ε)⋅ log n queries to f and in poly((log s)/ε)⋅ n log n time. This yields a tolerant tester that distinguishes functions that are close to size-s decision trees from those that are far from size-S decision trees. The polylogarithmic dependence on s in the efficiency of our tester is exponentially smaller than that of existing testers. Since decision tree complexity is well known to be related to numerous other boolean function properties, our results also provide a new algorithm for reconstructing and testing these properties. 

   more » « less
4. Approximating the Distance to Monotonicity of Boolean Functions

   https://doi.org/10.1137/1.9781611975994.123  

   Pallavoor, Ramesh Krishnan; Raskhodnikova, Sofya; Waingarten, Erik (January 2020, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020)

   We design a nonadaptive algorithm that, given a Boolean function f: {0, 1}^n → {0, 1} which is α-far from monotone, makes poly(n, 1/α) queries and returns an estimate that, with high probability, is an O-tilde(\sqrt{n})-approximation to the distance of f to monotonicity. Furthermore, we show that for any constant k > 0, approximating the distance to monotonicity up to n^(1/2−k)-factor requires 2^{n^k} nonadaptive queries, thereby ruling out a poly(n, 1/α)-query nonadaptive algorithm for such approximations. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. Approximating the distance to a property is closely related to tolerantly testing that property. Our lower bound stands in contrast to standard (non-tolerant) testing of monotonicity that can be done nonadaptively with O-tilde(n/ε^2) queries. We obtain our lower bound by proving an analogous bound for erasure-resilient testers. An α-erasure-resilient tester for a desired property gets oracle access to a function that has at most an α fraction of values erased. The tester has to accept (with probability at least 2/3) if the erasures can be filled in to ensure that the resulting function has the property and to reject (with probability at least 2/3) if every completion of erasures results in a function that is ε-far from having the property. Our method yields the same lower bounds for unateness and being a k-junta. These lower bounds improve exponentially on the existing lower bounds for these properties. 

   more » « less
5. Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $$~O(n\sqrt{d})$$ Monotonicity Tester

   Hadley Black, Deeparnab Chakrabarty (June 2023, Proceedings of the annual ACM Symposium on Theory of Computing)

   The problem of testing monotonicity for Boolean functions on the hypergrid, $$f:[n]^d \to \{0,1\}$$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making $$\otilde(\eps^{-2}\sqrt{d})$$ queries. Up to polylog $$d$$ and $$\eps$$ factors, this bound matches the $$\widetilde{\Omega}(\sqrt{d})$$-query non-adaptive lower bound (Chen-De-Servedio-Tan (STOC 2015), Chen-Waingarten-Xie (STOC 2017)). For any $n > 2$, the optimal non-adaptive complexity was unknown. A previous result of the authors achieves a $$\otilde(d^{5/6})$$-query upper bound (SODA 2020), quite far from the $$\sqrt{d}$$ bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant $$n$$, up to $$\poly(\eps^{-1}\log d)$$ factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making $$\otilde(\eps^{-2}n\sqrt{d})$$ queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid $[n]^d$. These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube. 

   more » « less