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

SIAM Journal on Computing

Computing with Noisy Information

Uriel Feige, Prabhakar Raghavan, David Peleg, Eli Upfal

Published Oct 1, 1994• 303 citations
Publisher

Abstract

This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tight bounds are given on the number of queries to input variables required to compute threshold functions, the parity function and symmetric functions. In the noisy comparison tree model, tight bounds are given on the number of noisy comparisons for searching, sorting, selection and merging. The paper also studies parallel selection and sorting with noisy comparisons, giving tight bounds for several problems.

DOI
10.1137/s0097539791195877

Related papers

Lower bounds for noisy Boolean decision trees

William Evans, Nicholas J. Pippenger

We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuck and Schmeltz) that almost all Boolean functions of n arguments require Ω(n log n) queries and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan and Upfal) that the parity function of n arguments requires Ω(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreigh, Hastad, Rudich and Smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1996•84 citations

Average-Case Lower Bounds for Noisy Boolean Decision Trees

William Evans, Nicholas J. Pippenger

We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuk and Schmeltz) that almost all Boolean functions of n arguments require $\Me(n \log n)$ queries, and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan, and Upfal) that the parity function of n arguments requires $\Me(n \log n)$ queries and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreich, Hastad, Rudich, and Smolensky, and it yields nonlinear lower bounds whenever the resiliency is asymptotic to the number of arguments.

SIAM Journal on Computing•Jan 1, 1998•17 citations

Noisy Computing of the Threshold Function

Ziao Wang, Nadim Ghaddar, Banghua Zhu +1 more

Let $\mathsf{TH}_k$ denote the $k$-out-of-$n$ threshold function: given $n$ input Boolean variables, the output is $1$ if and only if at least $k$ of the inputs are $1$. We consider the problem of computing the $\mathsf{TH}_k$ function using noisy readings of the Boolean variables, where each reading is incorrect with some fixed and known probability $p \in (0,1/2)$. As our main result, we show that it is sufficient to use $(1+o(1)) \frac{n\log \frac{m}δ}{D_{\mathsf{KL}}(p \| 1-p)}$ queries in expectation to compute the $\mathsf{TH}_k$ function with a vanishing error probability $δ= o(1)$, where $m\triangleq \min\{k,n-k+1\}$ and $D_{\mathsf{KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\mathsf{Bern}(p)$ and $\mathsf{Bern}(1-p)$ distributions. Conversely, we show that any algorithm achieving an error probability of $δ= o(1)$ necessitates at least $(1-o(1))\frac{(n-m)\log\frac{m}δ}{D_{\mathsf{KL}}(p \| 1-p)}$ queries in expectation. The upper and lower bounds are tight when $m=o(n)$, and are within a multiplicative factor of $\frac{n}{n-m}$ when $m=Θ(n)$. In particular, when $k=n/2$, the $\mathsf{TH}_k$ function corresponds to the $\mathsf{MAJORITY}$ function, in which case the upper and lower bounds are tight up to a multiplicative factor of two. Compared to previous work, our result tightens the dependence on $p$ in both the upper and lower bounds.

arXiv:2403.07227•IEEE Transactions on Information Theory•Aug 6, 2026•0 citations

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold

Yuzhou Gu, Xin Jun Li, Yinzhan Xu

In the noisy query model, the (binary) return value of every query (possibly repeated) is independently flipped with some fixed probability $p \in (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 $Θ(n\log n)$. 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 $Θ(n^2 \log n)$. 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\pm o(1)) \frac{n\log (\min\{k,n-k+1\}/δ)}{(1-2p)\log \frac{1-p}p}$ 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\pm o(1)) \frac{n\log (\min\{k+1,n-k+1\}/δ)}{(1-2p)\log \frac{1-p}p}$ 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.

arXiv:2502.04632•Feb 7, 2025•0 citations

Rounds vs queries trade-off in noisy computation

Navin Goyal, Michael Saks

We show that a noisy parallel decision tree making O(n) queries needs Ω(log ∗ n) rounds to compute OR of n bits. This answers a question of Newman [IEEE Conference on Computational Complexity, 2004, 113–124]. We prove more general trade-offs between the number of queries and rounds. We also settle a similar question for computing MAX in the noisy comparison tree model; these results bring out interesting differences among the noise models. 1

Symposium on Discrete Algorithms•Jan 23, 2005•1 citation

Sensitivity and Query Complexity under Uncertainty

Benson, Deepu, Komarath, Balagopal, Nikhil S. Mande +3 more

In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output ''unknown'' only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its hazard-free extension. - We prove an analogue of Huang's celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. - We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. - We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. - We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. - We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function.

arXiv:2507.00148•Jun 30, 2025•0 citations
This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tight bounds are given on the number of queries to input variables required to compute threshold functions, the parity function and symmetric functions. In the noisy comparison tree model, tight bounds are given on the number of noisy comparisons for searching, sorting, selection and merging. The paper also studies parallel selection and sorting with noisy comparisons, giving tight bounds for several problems.
We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuck and Schmeltz) that almost all Boolean functions of n arguments require Ω(n log n) queries and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan and Upfal) that the parity function of n arguments requires Ω(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreigh, Hastad, Rudich and Smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.
We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuk and Schmeltz) that almost all Boolean functions of n arguments require $\Me(n \log n)$ queries, and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan, and Upfal) that the parity function of n arguments requires $\Me(n \log n)$ queries and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreich, Hastad, Rudich, and Smolensky, and it yields nonlinear lower bounds whenever the resiliency is asymptotic to the number of arguments.
Let THk\mathsf{TH}_kTHk​ denote the kkk-out-of-nnn threshold function: given nnn input Boolean variables, the output is 111 if and only if at least kkk of the inputs are 111. We consider the problem of computing the THk\mathsf{TH}_kTHk​ function using noisy readings of the Boolean variables, where each reading is incorrect with some fixed and known probability p∈(0,1/2)p \in (0,1/2)p∈(0,1/2). As our main result, we show that it is sufficient to use (1+o(1))nlog⁡mδDKL(p∥1−p)(1+o(1)) \frac{n\log \frac{m}δ}{D_{\mathsf{KL}}(p \| 1-p)}(1+o(1))DKL​(p∥1−p)nlogδm​​ queries in expectation to compute the THk\mathsf{TH}_kTHk​ function with a vanishing error probability δ=o(1)δ= o(1)δ=o(1), where m≜min⁡{k,n−k+1}m\triangleq \min\{k,n-k+1\}m≜min{k,n−k+1} and DKL(p∥1−p)D_{\mathsf{KL}}(p \| 1-p)DKL​(p∥1−p) denotes the Kullback-Leibler divergence between Bern(p)\mathsf{Bern}(p)Bern(p) and Bern(1−p)\mathsf{Bern}(1-p)Bern(1−p) distributions. Conversely, we show that any algorithm achieving an error probability of δ=o(1)δ= o(1)δ=o(1) necessitates at least (1−o(1))(n−m)log⁡mδDKL(p∥1−p)(1-o(1))\frac{(n-m)\log\frac{m}δ}{D_{\mathsf{KL}}(p \| 1-p)}(1−o(1))DKL​(p∥1−p)(n−m)logδm​​ queries in expectation. The upper and lower bounds are tight when m=o(n)m=o(n)m=o(n), and are within a multiplicative factor of nn−m\frac{n}{n-m}n−mn​ when m=Θ(n)m=Θ(n)m=Θ(n). In particular, when k=n/2k=n/2k=n/2, the THk\mathsf{TH}_kTHk​ function corresponds to the MAJORITY\mathsf{MAJORITY}MAJORITY function, in which case the upper and lower bounds are tight up to a multiplicative factor of two. Compared to previous work, our result tightens the dependence on ppp in both the upper and lower bounds.
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)p \in (0, 1/2)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)Ω(n)Ω(n) has noisy query complexity Θ(nlog⁡n)Θ(n\log n)Θ(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 Θ(n2log⁡n)Θ(n^2 \log n)Θ(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 kkk-Threshold problem and the Counting problem. The kkk-Threshold problem asks to decide whether there are at least kkk ones among nnn bits, given noisy query access to the bits. We prove that (1±o(1))nlog⁡(min⁡{k,n−k+1}/δ)(1−2p)log⁡1−pp(1\pm o(1)) \frac{n\log (\min\{k,n-k+1\}/δ)}{(1-2p)\log \frac{1-p}p}(1±o(1))(1−2p)logp1−p​nlog(min{k,n−k+1}/δ)​ queries are both sufficient and necessary to achieve error probability δ=o(1)δ= o(1)δ=o(1). Previously, such a result was only known when min⁡{k,n−k+1}=o(n)\min\{k,n-k+1\}=o(n)min{k,n−k+1}=o(n) [Wang, Ghaddar, Zhu and Wang, arXiv 2024]. We also show a similar (1±o(1))nlog⁡(min⁡{k+1,n−k+1}/δ)(1−2p)log⁡1−pp(1\pm o(1)) \frac{n\log (\min\{k+1,n-k+1\}/δ)}{(1-2p)\log \frac{1-p}p}(1±o(1))(1−2p)logp1−p​nlog(min{k+1,n−k+1}/δ)​ bound for the Counting problem, where one needs to count the number of ones among nnn bits given noisy query access and kkk denotes the answer.
In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output ''unknown'' only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its hazard-free extension. - We prove an analogue of Huang's celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. - We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. - We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. - We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. - We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function.