Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1702.06997 · ACM Symposium on Theory of Computing (STOC)

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

Xi Chen, Erik Waingarten, Jinyu Xie

Published Jun 15, 2017• 55 citations
arXivHTMLPDF

Abstract

We prove a lower bound of Ω(n1/3) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f:{0,1}n→ {0,1} is monotone versus far from monotone. This improves the recent lower bound of Ω(n1/4) for the same problem by Belovs and Blais (STOC'16). Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrand's random DNFs.

DOI
10.1145/3055399.3055461

Related papers

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces

Xi Chen, Rocco A. Servedio, Li-Yang Tan +1 more

We give a poly(log(n),1/epsilon)-query adaptive algorithm for testing whether an unknown Boolean function f:{-1, 1}^n -> {-1, 1}, which is promised to be a halfspace, is monotone versus epsilon-far from monotone. Since non-adaptive algorithms are known to require almost Omega(n^{1/2}) queries to test whether an unknown halfspace is monotone versus far from monotone, this shows that adaptivity enables an exponential improvement in the query complexity of monotonicity testing for halfspaces.

arXiv:1706.05556•Leibniz international proceedings in informatics•Jan 1, 2017•1 citation

Relative-Error Unateness Testing

Xi Chen, Diptaksho Palit, Kabir Peshawaria +3 more

The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider the problem of relative-error testing an unknown and arbitrary $f: \{0,1\}^n \to \{0,1\}$ for the property of being a unate function, i.e. a function that is either monotone non-increasing or monotone non-decreasing in each of the $n$ input variables. Our first result is a one-sided non-adaptive algorithm for this problem that makes $\tilde{O}(\log(N)/ε)$ samples and queries, where $N=|f^{-1}(1)|$ is the number of satisfying assignments of the function that is being tested and the value of $N$ is given as an input parameter to the algorithm. Building on this algorithm, we next give a one-sided adaptive algorithm for this problem that does not need to be given the value of $N$ and with high probability makes $\tilde{O}(\log(N)/ε)$ samples and queries. We also give lower bounds for both adaptive and non-adaptive two-sided algorithms that are given the value of $N$ up to a constant multiplicative factor. In the non-adaptive case, our lower bounds essentially match the complexity of the algorithm that we provide.

arXiv:2510.21589•Leibniz international proceedings in informatics•Oct 24, 2025•2 citations

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries

Chen, Mark, Xi Chen, Hao Xuan Cui +2 more

We show that for any constant $c>0$, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity $Ω(n^{1/2-c})$. This improves the $\tildeΩ(n^{1/3})$ lower bound of [CWX17] and almost matches the $\tilde{O}(\sqrt{n})$ upper bound of [KMS18].

arXiv:2511.04558•Nov 6, 2025•2 citations

The non-adaptive query complexity of testing k-parities

Harry Buhrman, David García-Soriano, Arie Matsliah +1 more

We prove tight bounds of Θ(k log k) queries for non-adaptively testing whether a function f : {0, 1} n → {0, 1} is a k-parity or far from any k-parity.The lower bound combines a recent method of Blais, Brody and Matulef [4] to get lower bounds for testing from communication complexity with an Ω(k log k) lower bound for the one-way communication complexity of k-disjointness.

arXiv:1209.3849•Chicago Journal of Theoretical Computer Science•Jan 1, 2013•33 citations

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +2 more

The Total Influence ( Average Sensitivity ) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function, which we denote by I [ f ]. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of (1 ± ε ) by performing O (√ n I [ f ] poly(1/ ε )) queries. We also prove a lower bound of Ω (√ n log n · I [ f ]) on the query complexity of any constant factor approximation algorithm for this problem (which holds for I [ f ]= Ω (1)), hence showing that our algorithm is almost optimal in terms of its dependence on n . For general functions, we give a lower bound of Ω ( n I [ f ]), which matches the complexity of a simple sampling algorithm.

arXiv:1101.5345•ACM Transactions on Computation Theory•Nov 1, 2012•29 citations

Approximating the Noise Sensitivity of a Monotone Boolean Function

Ronitt Rubinfeld, Arsen Vasilyan

The noise sensitivity of a Boolean function f: {0,1}^n - > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noise-sensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]). Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/- epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm’s query complexity is close to optimal in terms of its dependence on n. We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.

arXiv:1904.06745•Leibniz international proceedings in informatics•Jan 1, 2019•2 citations
We prove a lower bound of Ω(n1/3) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f:{0,1}n→ {0,1} is monotone versus far from monotone. This improves the recent lower bound of Ω(n1/4) for the same problem by Belovs and Blais (STOC'16). Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrand's random DNFs.
The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider the problem of relative-error testing an unknown and arbitrary f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\}f:{0,1}n→{0,1} for the property of being a unate function, i.e. a function that is either monotone non-increasing or monotone non-decreasing in each of the nnn input variables. Our first result is a one-sided non-adaptive algorithm for this problem that makes O~(log⁡(N)/ε)\tilde{O}(\log(N)/ε)O~(log(N)/ε) samples and queries, where N=∣f−1(1)∣N=|f^{-1}(1)|N=∣f−1(1)∣ is the number of satisfying assignments of the function that is being tested and the value of NNN is given as an input parameter to the algorithm. Building on this algorithm, we next give a one-sided adaptive algorithm for this problem that does not need to be given the value of NNN and with high probability makes O~(log⁡(N)/ε)\tilde{O}(\log(N)/ε)O~(log(N)/ε) samples and queries. We also give lower bounds for both adaptive and non-adaptive two-sided algorithms that are given the value of NNN up to a constant multiplicative factor. In the non-adaptive case, our lower bounds essentially match the complexity of the algorithm that we provide.
Boolean function monotonicity testing requires (almost) n1/2n^{1/2}n1/2 queries
We show that for any constant c>0c>0c>0, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity Ω(n1/2−c)Ω(n^{1/2-c})Ω(n1/2−c). This improves the Ω~(n1/3)\tildeΩ(n^{1/3})Ω~(n1/3) lower bound of [CWX17] and almost matches the O~(n)\tilde{O}(\sqrt{n})O~(n​) upper bound of [KMS18].
The Total Influence ( Average Sensitivity ) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function, which we denote by I [ f ]. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of (1 ± ε ) by performing O (√ n I [ f ] poly(1/ ε )) queries. We also prove a lower bound of Ω (√ n log n · I [ f ]) on the query complexity of any constant factor approximation algorithm for this problem (which holds for I [ f ]= Ω (1)), hence showing that our algorithm is almost optimal in terms of its dependence on n . For general functions, we give a lower bound of Ω ( n I [ f ]), which matches the complexity of a simple sampling algorithm.
The noise sensitivity of a Boolean function f: {0,1}^n - > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noise-sensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]). Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/- epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm’s query complexity is close to optimal in terms of its dependence on n. We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.