More Like this

1. 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
2. Property testing with online adversaries

   Ben-Eliezer, Omri; Kelman, Esty; Meir, Uri; Raskhodnikova, Sofya (January 2024, Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS))

   The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Specifically, after each query made by the tester is answered, the adversary can intervene and either erase or corrupt t data points. In this work, we investigate a more nuanced version of the online model in order to overcome old and new impossibility results for the original model. We start by presenting an optimal tester for linearity and a lower bound for low-degree testing of Boolean functions in the original model. We overcome the lower bound by allowing batch queries, where the tester gets a group of queries answered between manipulations of the data. Our batch size is small enough so that function values for a single batch on their own give no information about whether the function is of low degree. Finally, to overcome the impossibility results of Kalemaj et al. for sortedness and the Lipschitz property of sequences, we extend the model to include t < 1, i.e., adversaries that make less than one erasure per query. For sortedness, we characterize the rate of erasures for which online testing can be performed, exhibiting a sharp transition from optimal query complexity to impossibility of testability (with any number of queries). Our online tester works for a general class of local properties of sequences. One feature of our results is that we get new (and in some cases, simpler) optimal algorithms for several properties in the standard property testing model. 

   more » « less
3. A $$d^{1/2+o(1)}$$ Monotonicity Tester for Boolean Functions on $$d$$-Dimensional Hypergrids

   Hadley Black, Deeparnab Chakrabarty (November 2023, Annual Symposium on Foundations of Computer Science)

   Monotonicity testing of Boolean functions on the hypergrid, $$f:[n]^d \to \{0,1\}$$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $$n$$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $$\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$$. This complexity is independent of $$n$$, but has a suboptimal dependence on $$d$$. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe $$\widetilde{O}(\varepsilon^{-2} n^3\sqrt{d})$$ and $$\widetilde{O}(\varepsilon^{-2} n\sqrt{d})$$-query testers, respectively. These testers have an almost optimal dependence on $$d$$, but a suboptimal polynomial dependence on $$n$$. \smallskip In this paper, we describe a non-adaptive, one-sided monotonicity tester with query complexity $$O(\varepsilon^{-2} d^{1/2 + o(1)})$$, \emph{independent} of $$n$$. Up to the $$d^{o(1)}$$-factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of $$n$$ yields a non-adaptive, one-sided $$O(\varepsilon^{-2} d^{1/2 + o(1)})$$-query monotonicity tester for Boolean functions $$f:\mathbb{R}^d \to \{0,1\}$$ associated with an arbitrary product measure. 

   more » « less
4. 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
5. 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