A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions

Yuzhou Gu, Xin Li, Yinzhan XuarXiv 2026 · arXiv

TL;DR

This paper introduces a powerful, unified framework for proving lower bounds on the noisy query complexity of Boolean functions by analyzing the structural properties of subgraphs within the Boolean hypercube. Using this approach, the authors resolve a recent open conjecture by proving that a function's noisy query complexity is fundamentally bounded by its total influence, while simultaneously simplifying and unifying several classic lower-bound proofs.

What Problem Does This Paper Address?

In modern computing, data transmission and hardware operations are rarely perfectly reliable. To model this, computer scientists use the noisy query model. Imagine you want to compute a property of a hidden binary string (a Boolean function $f(x)$), and you can ask to see individual bits. However, every time you query a bit, there is a constant probability $p$ that the answer gets flipped. To be certain of your answer, you have to query bits multiple times and use clever strategies.

The minimum expected number of queries needed to compute the function with a low error probability is called its noisy query complexity ($N_p(f)$).

While designing algorithms for this model is well-studied, proving lower bounds—showing that no algorithm can do better than a certain threshold—is notoriously difficult. Historically, researchers had to invent bespoke, ad-hoc proofs for every single function (like PARITY or Graph-Connectivity). This paper addresses this gap by providing the first general, unified framework to derive these lower bounds for arbitrary Boolean functions.

Methods

The authors bridge the gap between query complexity and graph theory. They represent the inputs as a Boolean hypercube (a graph where each vertex is a binary string, and edges connect strings that differ by exactly one bit). They then define a specific subgraph, $H_f$, by keeping only the edges where the function's output changes (i.e., $f(x) \neq f(y)$).

The core technical contribution is Theorem 2, which establishes a lower bound based on the degree statistics of these subgraphs.

To prove this, they utilize a standard theoretical tool called the three-phase framework:

  1. Phase 1: An algorithm queries bits non-adaptively.
  2. Phase 2: An "oracle" reveals some bits for free.
  3. Phase 3: The algorithm makes a limited number of adaptive, exact queries.

The authors introduce a novel, graph-theoretic "hard distribution" ($\mu$) based on the degrees of the vertices in the subgraph. They prove a Balance Lemma, demonstrating that even after the first two phases reveal information, the posterior probability of the function being 0 or 1 remains perfectly balanced (close to 50/50). This implies that the algorithm is still essentially guessing, forcing a high query complexity in Phase 3.

Datasets

Not discussed in the paper. This is a purely theoretical paper in mathematical computer science and does not use empirical datasets or benchmarks.

Key Insights and Ideas

  • The Power of Degeneracy: The authors connect noisy query complexity to graph degeneracy (the minimum degree of vertices in any subgraph). Because a graph's average degree (which corresponds to the function's total influence) is mathematically bounded by its degeneracy, graph theory naturally yields complexity bounds.
  • Resolution of the COLT 2025 Conjecture: The paper definitively answers an open problem by proving that $N_p(f) = \Omega(I(f) \log I(f))$, where $I(f)$ is the total influence of the function. This means a function's sensitivity to its inputs inherently dictates a logarithmic penalty when noise is introduced.
  • Radical Simplification: Instead of analyzing complex combinatorial structures from scratch—such as the uniform spanning trees required in previous proofs for Graph-Connectivity—researchers can now simply plug a function into this paper's general theorem to get a tight lower bound.

Key Results

  • Unified Lower Bounds: The framework successfully recovers the tight lower bounds for several well-known problems, including $k$-THRESHOLD, symmetric functions, and Graph-Connectivity ($\Omega(N^2 \log N)$), under a single umbrella.
  • New Lower Bounds: The authors applied their theorem to discover tight lower bounds for entirely new classes of functions:
  • Biased Random Functions: Proved a lower bound of $\Omega(n \log n)$ even when the function outputs 1 with a very low, size-dependent probability.
  • Subsequence Counting: Proved that counting how many times a specific pattern appears as a subsequence in a binary string requires $\Omega(n \log n)$ noisy queries.

Limitations and Future Work

The authors note that their general lower bound is not always tight. The maximum lower bound that can be extracted using their subgraph degree technique is bounded by $\Omega(s(f) \log s(f))$, where $s(f)$ is the maximum sensitivity of the function.

However, there are known functions where the standard randomized query complexity ($R(f)$) is strictly larger than $s(f) \log s(f)$. In those cases, this new framework will underestimate the true difficulty of the problem. Developing a general framework that remains tight even for these highly asymmetric functions remains an open challenge.

Summary updated

Abstract

We study the query complexity of Boolean functions $f: \{0, 1\}^n \rightarrow \{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 \in (0, 1/2)$; repeated queries are allowed. The noisy query complexity $\mathsf{N}_p(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 $\mathsf{N}_p(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 $\mathsf{N}_p(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 $\mathsf{N}_p(f) = Ω(\mathsf{I}(f) \log \mathsf{I}(f))$, where $\mathsf{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.
BibTeX
@misc{gu2026unified,
  author = {Yuzhou Gu and Xin Li and Yinzhan Xu},
  title = {{A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions}},
  year = {2026},
  eprint = {2606.11448},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.11448},
}

Loading related content...

Figure