The {\em Total Influence} ({\em 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 \ifnum\plusminus=1 $f: \{\pm1\}^n \longrightarrow \{\pm1\}$, \else $f: \bitset^n \to \bitset$, \fi 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\pm \eps)$ by performing $O(\frac{\sqrt{n}\log n}{I[f]} \poly(1/\eps)) $ queries. % \mnote{D: say something about technique?} We also prove a lower bound of % $Ω(\frac{\sqrt{n/\log n}}{I[f]})$ $Ω(\frac{\sqrt{n}}{\log n \cdot I[f]})$ on the query complexity of any constant-factor approximation algorithm for this problem (which holds for $I[f] = Ω(1)$), % and $I[f] = O(\sqrt{n}/\log n)$), hence showing that our algorithm is almost optimal in terms of its dependence on $n$. For general functions we give a lower bound of $Ω(\frac{n}{I[f]})$, which matches the complexity of a simple sampling algorithm.
The {\em Total Influence} ({\em 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 \ifnum\plusminus=1 f:{±1}n⟶{±1}, \else f:\bitsetn→\bitset, \fi 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±\eps) by performing O(I[f]nlogn\poly(1/\eps)) queries. % \mnote{D: say something about technique?} We also prove a lower bound of % Ω(I[f]n/logn)Ω(logn⋅I[f]n) on the query complexity of any constant-factor approximation algorithm for this problem (which holds for I[f]=Ω(1)), % and I[f]=O(n/logn)), hence showing that our algorithm is almost optimal in terms of its dependence on n. For general functions we give a lower bound of Ω(I[f]n), which matches the complexity of a simple sampling algorithm.
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.
We study how large the certificate complexity C(f) of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function f whose randomized query complexity with one-sided error satisfies R1(f)=Θ(C(f)). This separation is optimal even when two-sided error is allowed.
From this construction, we obtain another total Boolean function F with bounded-error quantum query complexity Q(F)=O(C(F)1/4), attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are O(C(F)). We also prove matching lower bounds for these two measures on F.
We study the query complexity of Boolean functions f:{0,1}n→{0,1} in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In this model, an algorithm can adaptively query the bits of an input vector, but each query result is independently flipped with constant probability p∈(0,1/2); repeated queries are allowed. The noisy query complexity Np(f) of a function f is defined as the minimum expected number of queries needed to compute f(x) with error probability at most 1/3, for the worst case input x. We prove a general lower bound on Np(f) based on degree statistics of certain subgraphs of the Boolean hypercube. This is the first general lower bound beyond those implied by the simple observation that Np(f) is lower bounded by the randomized query complexity. We show that this recovers (up to a constant factor) most previously known lower bounds on the noisy query complexity of Boolean functions, providing a unified framework for understanding these results and simplifying the proofs in several cases. Furthermore, this resolves in the affirmative an open problem of Gu, Li and Xu [COLT 2025] that Np(f)=Ω(I(f)logI(f)), where I(f) denotes the total influence of f. We also apply our general lower bound to obtain tight bounds on the noisy query complexity for several new functions.
In the noisy query model, the (binary) return value of every query (possibly repeated) is independently flipped with some fixed probability p∈(0,1/2). In this paper, we obtain tight bounds on the noisy query complexity of several fundamental problems. Our first contribution is to show that any Boolean function with total influence Ω(n) has noisy query complexity Θ(nlogn). Previous works often focus on specific problems, and it is of great interest to have a characterization of noisy query complexity for general functions. Our result is the first noisy query complexity lower bound of this generality, beyond what was known for random Boolean functions [Reischuk and Schmeltz, FOCS 1991]. Our second contribution is to prove that Graph Connectivity has noisy query complexity Θ(n2logn). In this problem, the goal is to determine whether an undirected graph is connected using noisy edge queries. While the upper bound can be achieved by a simple algorithm, no non-trivial lower bounds were known prior to this work. Last but not least, we determine the exact number of noisy queries (up to lower order terms) needed to solve the k-Threshold problem and the Counting problem. The k-Threshold problem asks to decide whether there are at least k ones among n bits, given noisy query access to the bits. We prove that (1±o(1))(1−2p)logp1−pnlog(min{k,n−k+1}/δ) queries are both sufficient and necessary to achieve error probability δ=o(1). Previously, such a result was only known when min{k,n−k+1}=o(n) [Wang, Ghaddar, Zhu and Wang, arXiv 2024]. We also show a similar (1±o(1))(1−2p)logp1−pnlog(min{k+1,n−k+1}/δ) bound for the Counting problem, where one needs to count the number of ones among n bits given noisy query access and k denotes the answer.