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 prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard the computation as a communication process in which the oracle and the computer exchange several rounds of messages, each round consisting of O(log(n)) bits. Let E(f) be the Shannon entropy of the random variable f(X), where X is uniformly random in f's domain. Our main result is that it takes Ω(E(f)) queries to compute any \emph{total} function f. It is interesting to contrast this bound with the Ω(E(f)/log(n)) bound, which is tight for \emph{partial} functions. Our approach is the polynomial method.
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.
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.
In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function f is the minimum number of probes made by any query algorithm that computes f. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to ”approximately ” compute f) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). The main results in this thesis are: • We study the relation between deterministic decision tree complexity and other combinatorial measures of complexity measures like sensitivity and block sensitivity. We prove that for minterm-transitive functions the sensitivity is quadratically related to block sensitivity which is polynomially
This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.