7. Query Hierarchy Theorems

The last two lectures showed that even the most basic questions “Does randomness help reduce query complexity?” and “If so, by how much?” lead to surprisingly rich lines of research. Let us now continue along this line by asking another deceptively simple question:

What values can $R (f)$ take?

Every non-constant function $f : {0, 1}^{n} \to {0, 1}$ has query complexity bounded below by $R (f) \geq 1$ and above by $R (f) \leq n$ . Are there functions with each of the possible query complexities in between those two extremes? And what about when we restrict our attention to various classes of functions? Such questions give rise to Query Hierarchy Theorems (and some associated Gap Theorems).

But before we dive into these questions, let’s first take a detour and examine the randomized query complexity of two special functions.

Parity and Gap Majority

The parity (or XOR) function on $n$ bits is the total Boolean function ${Parity}_{n} : {0, 1}^{n} \to {0, 1}$ defined by

{Parity}_{n} (x) = x_{1} \oplus x_{2} \oplus \dots \oplus x_{n} = \sum_{i = 1}^{n} x_{i} (\mod 2) .

With an adversary argument, we can show that $D ({Parity}_{n}) = n$ . (In fact, the adversary argument shows the even stronger claim that every leaf of a decision tree that computes the parity function must have depth $n$ .) We can also show that the bounded-error randomized query complexity of the parity function is $R_{ϵ} ({Parity}_{n}) = Ω (n)$ for any constant $ϵ < \frac{1}{2}$ bounded away from $\frac{1}{2}$ .

And even in the small bias regime where we consider $ϵ = \frac{1}{2} - δ$ for some $δ = δ (n)$ (think for example of $δ = 1 / \sqrt{n}$ ) then we still have a large lower bound on the query complexity of the function.

Proposition. For every bias function $δ : N \to N$ ,
${\overset{―}{R}}_{\frac{1}{2} - δ (n)} ({Parity}_{n}) = Θ (δ (n) \cdot n) .$
In particular, ${\overset{―}{R}}_{\frac{1}{2} - \frac{1}{\sqrt{n}}} ({Parity}_{n}) = Θ (\sqrt{n}) .$

As we will see, the parity function is useful in establishing a number of complexity theoretic results. Another useful function for query complexity in particular is the gap majority function on $n$ bits. It is the partial function defined over ${0, 1}^{n}$ by

{GapMaj}_{n} (x) = {\begin{cases} 1 & if ‖ x ‖_{1} \geq \frac{n}{2} + \sqrt{n} \\ 0 & if ‖ x ‖_{1} \leq \frac{n}{2} - \sqrt{n} \\ * & otherwise . \end{cases}

In other words, the gap majority function is the usual Majority function restricted to the domain

X = {x \in {0, 1}^{n} : | ‖ x ‖_{1} - \frac{n}{2} | \geq \sqrt{n}} .

The restriction on the domain makes the function a little bit easier to compute than the standard majority function because it guarantees a gap of size at least $\sqrt{n}$ between the input bits that agree with the value of the function and the ones that don’t. This gap is not large enough, however, to affect the bounded-error randomized query complexity of the function: when $ϵ$ is bounded away from $\frac{1}{2}$ , then $R_{ϵ} ({GapMaj}_{n}) = Ω (n) .$

In the small bias regime, however, the gap does make a meaningful difference.

Proposition. For every bias function $δ : N \to N$ ,
${\overset{―}{R}}_{\frac{1}{2} - δ (n)} ({GapMaj}_{n}) = Θ (δ (n)^{2} \cdot n) .$
In particular, ${\overset{―}{R}}_{\frac{1}{2} - \frac{1}{\sqrt{n}}} ({GapMaj}_{n}) = O (1) .$

Note that this bound is must stronger in terms of $δ$ than the corresponding bound for the parity function. In particular, this bound says that $O (1)$ queries suffice to comput the gap majority function with bias $δ (n) = 1 / \sqrt{n}$ . (Indeed, querying a single bit chosen uniformly at random and returning its value gives a randomized algorithm for gap majority with success probability $\frac{1}{2} + \sqrt{n}$ .) By contrast, our bound on the parity function implies that any randomized algorithm with the same bias must have query complexity $Ω (\sqrt{n})$ .

A Hierarchy Gap Theorem

Using the parity function on a subset of the $n$ bits in the domain, we can easily show that for every function $q : N \to N$ and every $n \in N$ , there is a function $f : {0, 1}^{n} \to {0, 1}$ with query complexity $R_{\frac{1}{3}} (f) = Θ (q (n))$ .

But the observation above is not entirely satisfactory because the functions used in the construction only depend on a subset of the $n$ bits of the input. Such functions are called juntas, and what we would really like a hierarchy theorem sto show is that even ignoring all junta functions, we can still achieve all possible query complexities.

Definition. A total function $f : {0, 1}^{n} \to {0, 1}$ is truly $n$ -variate if for every input $i \in [n]$ , there exists an input $x \in {0, 1}^{n}$ such that $f (x) \neq f (x^{(i)})$ .

Can truly $n$ -variate functions achieve all possible query complexities? In the deterministic setting, the answer is no.

Proposition. Every truly $n$ -variate Boolean function $f : {0, 1}^{n} \to {0, 1}$ has deterministic query complexity $D (f) \geq \log n$ . This bound is asymptotically tight: there exist such functions $f$ with $D (f) = O (\log n)$ .

Proof. The lower bound on $D (f)$ follows immediately from the observation that a binary tree of height $h$ contains at most $2^{h}$ nodes and that if $f$ is truly $n$ -variate, any decision tree that computes it must query all of the $n$ indices $x_{i}$ in at least one of the nodes.

Many different functions can be constructed to show that the $\log n$ bound is asymptotically tight. One particularly useful construction because of its versatility is the $Index$ function. This function on $n = k + 2^{k}$ bits interprets an input $x$ as a tuple $(a, y)$ , $a \in {0, 1}^{k}$ and $y \in {0, 1}^{2^{k}}$ and is defined by $Index (a, y) = y_{a} .$ In other words, it returns the value of the coordinate of $y$ indexed by the address $a$ . As we can verify directly, the function is truly $n$ variate and it can be computed by a deterministic decision tree of depth $a + 1 = O (\log n)$ .

What about for randomized query complexity? The simple argument that we used for deterministic decision trees no longer holds when we consider randomized decision tree, because the trees in the support of the distribution that corresponds to a randomized decision tree do not have to all have nodes that query all of the indices of the input. Yet, the same lower bound on the query complexity of truly $n$ -variate functions still holds.

Theorem. Every truly $n$ -variate Boolean function $f : {0, 1}^{n} \to {0, 1}$ has randomized query complexity $R_{\frac{1}{3}} (f) = Ω (\log n)$ .

Proof. The lower bound follows from a matching lower bound on the maximum sensitivity of truly $n$ -variate functions. This result that $s (f) = Ω (\log n)$ for every non-constant truly $n$ -variate function $f$ is due to Simon (1982).

The bound on the minimum randomized query complexity of truly $n$ -variate functions is again asymptotically tight by the $Index$ function.

And the set of all truly $n$ -variate functions can be restricted even further. For example, we can consider the set of monotone truly $n$ -variate functions or the set of all symmetric functions. In some cases, these further restrictions give much stronger gap theorems:

Theorem. Every non-constant symmetric function $f : {0, 1}^{n} \to {0, 1}$ has randomized query complexity $R_{\frac{1}{3}} (f) = Θ (n)$ .

And in other cases, the additional restrictions do not affect the minimum query complexity of functions:

Theorem. Every monotone truly $n$ -variate function $f : {0, 1}^{n} \to {0, 1}$ has randomized query complexity $R_{\frac{1}{3}} (f) = Ω (\log n)$ . This bound is tight for some monotone truly $n$ -variate functions.

Proof. The lower bound is the one that holds for all truly $n$ -variate functions.

For the matching upper bound, consider the monotone variant of the index function. This function is defined on $n = k + (\binom{k}{k / 2})$ bits for some even $k$ . We again consider the first $k$ bits to represent an address, but in this case only the strings $a \in {0, 1}^{k}$ with Hamming weight exactly $k / 2$ represent valid addresses. The $MonotoneIndex$ function is defined as the standard $Index$ function on valid addresses. On all other addresses, the function evaluates to 1 if the address has more 1s than 0s and to 0 otherwise. We can again verify directly that the function is monotone and truly $n$ -variate, and that it can be computed by a deterministic decision tree of depth $a + 1 = O (\log n)$ .

What about other classes of functions? One particularly interesting special case is the set of all transitive-symmetric Boolean functions, where $f : {0, 1}^{n} \to {0, 1}$ if for every pair of indices $i, j \in [n]$ , there exists a permutation $π$ of $[n]$ such that for every $x \in {0, 1}^{n}$ , the string $y = x_{π (1)} x_{π (2)} \dots x_{π (n)}$ satisfies $f (y) = f (x)$ . The randomized evasiveness conjecture for monotone graph properties discusssed in the first lecture is a special case of the following conjectured Gap Theorem for transitive-symmetric function:

Randomized Evasiveness Conjecture. Every non-constant monotone transitive-symmetric function $f : {0, 1}^{n} \to {0, 1}$ has randomized query complexity $R_{\frac{1}{3}} (f) = Θ (n)$ .

A Hierarchy Theorem for Partial Functions

If we turn our attention to partial Boolean functions, we can again easily obtain a hierarchy theorem for randomized query complexity. This time, we can start with the Gap Majority function and vary the size of the gap in Hamming weights in the definition of the domain $X$ of the function. As we saw above, when the gap has size $\sqrt{n}$ , the Gap Majority function has randomized query complexity $Ω (n)$ . At the other extreme, when the gap has size linear in $n$ , say $\frac{n}{4}$ , we see that the resulting (Large) Gap Majority function has query complexity $O (1)$ . And analyzing the possible gap lengths in between those two extremes gives functions with query complexity everywhere between $O (1)$ and $Ω (n)$ .

But again this answer is not completely satisfying. Or, perhaps a better way to put it is that this observation raises an immediate follow-up question: is it just the size of the gap (appropriately defined/generalized) that determines the randomized query complexity of all partial functions? We can make this question precise by introducing the notion of margin of partial functions.

Definition. The margin of the partial function $f : X \to {0, 1}$ for some $X \subseteq {0, 1}^{n}$ is the minimum Hamming distance between inputs in $X$ that take different values under $f$ :
$margin (f) = min {‖ x - y ‖_{1} : x, y \in X, f (x) \neq f (y)} .$

Let us say that the partial function $f : X \to {0, 1}$ , $X \subseteq {0, 1}^{n}$ , has linear margin when $margin (f) = Ω (n)$ . As we have seen with the large gap majority function, there exist some non-constant partial functions with linear margin that have constant randomized query complexity. Is that the case for all linear margin functions? Or is the randomized query complexity of all these functions bounded by some other sublinear function?

The answer is no: having a linear margin is not sufficient to guarantee having small randomized query complexity.

Theorem. There exists a partial function $f : X \to {0, 1}$ , $X \subseteq {0, 1}^{n}$ with $margin (f) = Ω (n)$ and randomized query complexity $R_{\frac{1}{3}} (f) = Ω (n)$ .

Proof sketch. Following Goldreich, Goldwasser, and Ron (1998), one way to prove the theorem is via error-correcting codes.

We know that there is a set $X \subseteq {0, 1}^{n}$ of $| X | = 2^{Ω (n)}$ points in the hypercube such that every pair of points in $X$ has Hamming distance $Ω (n)$ between them. (Taking $X$ to be a random set of points and removing any pair that does not satisfy the condition suffices to establish this claiim; there are also more explict constructions that can be used.)

Let us define $f : X \to {0, 1}$ by setting its value independently at random for each point in $X$ . The minimum distance between points in $X$ guarantees that $f$ has linear margin. And we can show that for any decision tree with query complexity $o (n)$ , the uniform distribution on points in $X$ leads to leaves that have almost the same probability of being reached by points in $f^{- 1} (0)$ and in $f^{- 1} (1)$ , so that no such decision tree can compute $f$ with bounded error.

Building on this result, we can obtain a full (asymptotic) hierarchy theorem for partial functions with linear margin.

Once again, we can ask about particular sets of partial functions with linear margins. Doing so leads to property testing, which considers the partial functions that arise when considering properties of combinatorial objects (such as graphs or functions) and the number of queries required to distinguish the objects that have the property from those that are far from having the same property.