Random Restrictions of Bounded Low Degree Polynomials Are Juntas

The analysis of Boolean functions is a vibrant field with connections and applications to diverse areas. While several outstanding results have been established for Boolean functions, the closely related class of bounded functions, i.e. those which take value in the real interval $[0,1]$ at every point of the Boolean cube, remains far less understood. Indeed, such bounded functions are of great significance. As mentioned in Dinur, Friedgut, Kindler and O’Donnell [7], “such bounded functions often arise naturally, particularly as weighted averages of boolean functions; e.g., as Fourier transforms of boolean functions, as noise-convolutions of boolean functions, in the context of random walks on the discrete cube, and in hardness-of approximation theory in computational complexity”, and it is often important to understand when such functions depend essentially only on a few number of coordinates.

In this work, we study the effects of random restrictions on such bounded functions of low degree. The study of random restrictions of Boolean functions has been invaluable for establishing circuit lower bounds ( see for example, [9, 10, 21]), proof complexity (see for example, [5, 11]), de-randomization (see for example, [12]), and several other areas. Our main result shows a remarkable similarity in the behavior of bounded functions with their Boolean cousins, when hit with random restrictions.

By now, it is worth recalling that a classical result of Dinur, Friedgut, Kindler and O’Donnell [7] showed that bounded functions whose Fourier tail above degree $k$ is $\le \exp (-O(k^2))$ are approximable by juntas with arity $\exp (O(k))$. They also showed that this result is tight in general. We are interested in the case when the function has small degree $d$. What additional structure follows from this stronger condition? To take cue on what to expect, let’s recall the case of Boolean functions. If $f:{\{\pm 1\}}^n\to \{0,1\}$ is a degree $d$ Boolean function, a seminal result of Beals, Buhrman, Cleve, Mosca, and de Wolf [4] shows that $f$ can be represented by a DNF of width $d^{O(1)}$. By the celebrated Hastad’s switching lemma, this implies that if $f$ is hit with a random restriction with survival probability $1/d^{O(1)}$, with high probability $f$ becomes constant. We show something similar is true for bounded functions as well: if $f:{\{\pm 1\}}^n\to [0,1]$ is a degree $d$, bounded function and $f$ is hit with a random restriction with survival probability $O(\log (d)/d)$, with high probability it can be well-approximated by a junta depending only on $\text{poly}(d)$ coordinates. This is despite the fact that the expected number of variables that remain alive is $O\left(n\cdot \frac{\log d}{d}\right)$.

This result has interesting consequences for the Aaronson-Ambainis conjecture, which we explain next.

One of the central open problems in the field of quantum query complexity is determining if there exists a partial function which is defined on a large fraction of the Boolean hypercube (say, constant) but whose quantum query complexity and classical query complexity are super-polynomially separated. The result of Beals et. al. [4] shows that no such separation is possible when the function is defined on the entire hypercube. On the other hand, functions for which we know such a separation (e.g. - Forrelation [1] , Bernstein-Vazirani [6]) are defined on an exponentially small fraction of the hypercube. A possible explanation as to why all known functions exhibiting large gaps between quantum and classical query complexity have very small support size would be the following folklore conjecture:

It is known that if $Q$ makes at most $q$ queries, then $P$ is given by a polynomial of degree at most $2q$. Although $P$ has more structure than any arbitrary low degree bounded polynomial, it is further conjectured that such structure is not necessary. In other words, we forget the fact that $P$ arises from a quantum query algorithm and instead try to construct a classical query algorithm for any bounded low-degree polynomial. This led to the following conjecture (also folklore).

Aaronson and Ambainis [2] proposed the following query algorithm to estimate $P$: suppose the variance of the function is sufficiently small. Then we terminate the query algorithm and output the average over the unqueried coordinates. If not, we query the coordinate with the highest influence and restrict the function according to the response received. We keep doing this until we have made too many queries or the variance has become sufficiently low. In order to show that this algorithm gives an accurate estimate, [2] observed that it is sufficient to prove the following conjecture.

As a side remark, we mention that O’Donnell et al. [18] had shown previously that functions which can be approximated by decision trees have a coordinate with high influence. So conjectures 3 and 4 are equivalent.

The Aaronson-Ambainis Conjecture has received significant attention in the past few years. In 2006, a result of Dinur, Friedgut, Kindler and O’Donnell [7] showed that the conjecture is true if $\mathrm{𝗉𝗈𝗅𝗒}(d)$ is replaced by $\exp (d)$. In 2012, Montanaro [16] proved the conjecture in the special case of block-multilinear forms where all coefficients have the same magnitude. In 2016, O’Donnell and Zhao [19] showed that it suffices to prove the conjecture for a special class of polynomials known as one-block decoupled polynomials. In 2020, Keller and Klein [13] claimed to have found a proof for the conjecture but their paper had a subtle flaw and turned out to be wrong. More recently, Lovett and Zhang [15] initiated a new line of attack using the notions of fractional block sensitivity and fractional certificate complexity. In 2022, Bansal, Sinha and de Wolf [3] proved that this conjecture is true for completely bounded block multilinear forms – a class of polynomials that captures a special kind of quantum query algorithms.

In this work, we show that Aaronson-Ambainis conjecture is true for a large fraction of random restrictions of $f$ assuming $\mathrm{𝖵𝖺𝗋}[f]$ is not too low. More precisely, we have:

We view this result as evidence that the Aaronson-Ambainis Conjecture is true, and hope it gives new insights into the conjecture.

We also observe that our result implies one of the two main unconditional results proven in a recent paper of Lovett and Zhang [15] about the existence of small sensitive blocks albeit with a slightly different set of parameters.

Let $f:{\{\pm 1\}}^n\to [0,1]$. An input $x\in {\{\pm 1\}}^n$ is said to be $(r,ϵ)$ sensitive if there exists a $y$ such that $d(x,y)\le r$ and $|f(x)-f(y)|\ge ϵ$. [15] proves the following:

An immediate consequence of our result is that at least $\mathrm{\Omega }({(\mathrm{𝖵𝖺𝗋}[f]/d)}^{O(1)})$ fraction of inputs are $(1,ϵ)$ sensitive where $ϵ=\text{poly}(\mathrm{𝖵𝖺𝗋}[f]/d)$. Thus, while we lose a bit in the fraction of sensitive inputs, we gain by letting our block size be exactly 1 instead of $\text{poly}(d,1/ϵ,\log (n))$. It is interesting to remark that our techniques and those of Lovett and Zhang seem quite different. We further remark that [15] shows that if one can show every input has a small sensitive block, Aaronson-Ambainis conjecture will follow.

We believe that Theorem 5 opens up some possible lines of attack to the Aaronson-Ambainis conjecture:

• $\mathrm{■}$

  Assuming a supposed counterexample $f:{\{\pm 1\}}^n\to [0,1]$, modify it appropriately (e.g., by composing it with some appropriate gadget or applying a low noise operator) to get a function $\tilde{f}:{\{\pm 1\}}^{\tilde{n}}\to [0,1]$ such that most of its random restrictions remain a counterexample. Combined with our result, this will prove Aaronson-Ambainis conjecture. This approach is discussed in a bit more detail in the conclusion.

• $\mathrm{■}$

  If we can construct a decision tree that queries $y$ (the input to the fixed part) in a few coordinates and outputs an influential coordinate of $f_y$ (the restricted function) with high probability, Aaronson-Ambainis conjecture will follow from the work of Keller and Klein. Again, this approach is discussed in a bit more detail in the conclusion.

We introduce notations and necessary preliminaries in section 3. We give a high level overview of our proof in section 4. In section 5 we compile some lemmas that will be needed in our main proof. Our main results are proven in section 6. Our main result is proven in section 6.2. It says that most random restrictions of a bounded low-degree function can be approximated by a small junta. In section 6.3 we prove that Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions.

The main result in this paper is a structural result for bounded low-degree functions similar in spirit to Hastad’s switching lemma [10]. Roughly speaking, we show that for come constant $C>0$, the following holds: let $f:{\{\pm 1\}}^n\to [0,1]$ be a polynomial of degree $d$, and let $\rho$ denote a random restriction with survival probability ${\displaystyle \frac{\log (d)}{Cd}}$. Then,

Once this is established, we can prove Aaronson-Ambainis conjecture for random restrictions as follows: it is easy to see that

This probability will be significantly more than the failure probability of the main result $\left({\displaystyle \frac{1}{d^{\mathrm{\Omega }(1)}}}\right)$ (this is the only place where we need the lower bound on $\mathrm{𝖵𝖺𝗋}[f]$). So for a $\mathrm{\Omega }(\mathrm{𝖵𝖺𝗋}[f]\log (d)/d)$ fraction of random restrictions, the variance of $f_{\rho }$ is high and $f_{\rho }$ can be well approximated by a junta with arity $\mathrm{𝗉𝗈𝗅𝗒}(d)$. This means one of the coordinates of the junta must have high influence. This concludes the proof.

Now we give a brief overview of how we prove the main result (Theorem 1). The starting point is the work by Dinur, Friedgut et al. [7] which states the following:

In other words, if the Fourier tail above a certain level $k$ is bounded, then $f$ can be well approximated by juntas of arity roughly $2^{O(k)}$.

We start with the observation that random restrictions have bounded Fourier tails (Lemma 15): if the function has degree $d$ and we make a random restriction with survival probability ${\displaystyle \frac{\log (d)}{Cd}}$ where $C>1$ is a large constant, using Chernoff bound we can show that with very high probability the Fourier weight above level $\log (d)$ will be low; around the order of $\exp (-\mathrm{\Omega }(C\log (d)))$. If we can manage to bring the Fourier weight above $\log (d)$ small enough so that Theorem 8 applies, then we will get that $f_{\rho }$ can be well approximated by a $\mathrm{𝗉𝗈𝗅𝗒}(d)$ junta. Unfortunately, if we try this, it turns out that we have to set the survival probability so low that on expectation the variance of $f_{\rho }$ goes down significantly as well. In other words, while it is true that $f_{\rho }$ can be well-approximated by juntas, it is for a trivial reason that its variance itself is very low. (And moreover, this is also true for functions $f:{\{\pm 1\}}^n\to ℝ$ that are merely $L^2$ bounded i.e, $𝖤[f^2]\le 1$, so we would not be using any additional structure that arises from the fact that $f$ is pointwise bounded.)

In order to make this approach work, we need to improve the tail bound $\exp (-O(k^2\log (k))/ϵ)$ in Theorem 8. The problematic term is the quadratic $\exp (-O(k^2))$ in the exponential. If the dominant term were to the order of $\exp (-O(k))$ instead, the calculations would go through. Can we hope to increase the tail bound to $\exp (-O(k))$ while paying a cost by increasing the junta arity? Unfortunately, again, this is not possible: [7] constructs a function which shows that the tail bound is essentially tight upto the $\log (k)$ factor - their function has ${\Vert f^{>k}\Vert }_2^2\approx \exp (-\mathrm{\Theta }(k^2))$ but approximating it to even $1/3$ accuracy requires reading $\mathrm{\Omega }(n)$ coordinates. Our key observation is that the function constructed by [7] has full degree whereas we are working with random restrictions of a low degree function, so in addition to the fact that the Fourier tail of $f_{\rho }$ above level $\log (d)$ is very small, we also know that $f_{\rho }$ has degree $d$. Can we hope to improve the tail bound in Theorem 8 if we have the additional restriction that the function is of degree $d$? Indeed, this turns out to be true. We prove the following result in section 6 (Theorem 28):

Below we briefly discuss how we are able to improve the tail bound under the additional degree assumption. Dinur et al [7] prove their tail bound (Theorem 8) by showing the following result (we are omitting the exact quantitative parameters here for reading convenience).

Let’s sketch how [7] proves Theorem 8 using Theorem 10. They assume $f$ is not approximable by $2^{O(k)}$ juntas - their goal is then to show that the Fourier tail above level $k$, ${\Vert f^{\ge k}\Vert }_2^2$, is large. To do so, they use Theorem 10: they take $h$ to be the truncated function $h=f^{\le k}$ and $g$ to be the original function $g=f$. This then lower bounds $𝖤[{(f-f^{\le k})}^2]$ which is precisely the Fourier tail above weight $k$. Thus, the distance lower bound $\epsilon$ in Theorem 10 governs the Fourier tail lower bound in Theorem 8. Since in Theorem 28 we have the additional information that $f$ is of degree $d$, for our purposes it will suffice to lower bound the distance of $h$ from bounded degree $d$ functions, not necessarily all bounded functions. In section 6.2 we prove a result of the following form (again, we are omitting the exact parameters for reading convenience; for the exact statement see Theorem 26).

The parameter $\tilde{\epsilon }$ in Theorem 11 is bigger than the corresponding $\epsilon$ parameter in Theorem 10 because we are only lower bounding the distance of $h$ from bounded low-degree functions whereas Theorem 10 lower bounds the distance of $h$ from arbitrary bounded functions. It turns out that the improvement in this parameter is sufficiently good for the calculations to go through.

In order to prove Theorem 11 we shall use the main idea of the proof of [7] along with a structural restriction for bounded low-degree functions proved first in Filmus et al. [8], and later used by Keller-Klein [13] and Lovett-Zhang [15]. Given any function $f:{\{\pm 1\}}^n\to ℝ$ and $x\in {\{\pm 1\}}^n$ define the block sensitivity of $f$ at $x$ to be

where the supremum ranges over all partitions $(B_1,B_2,\mathrm{\cdots },B_k)$ of the variables ($x^{(B_j)}$ denotes $x$ with the coordinates in $B_j$ flipped). Define the block sensitivity of $f$ to be $\text{bs}(f)={sup}_x\text{bs}(f,x)$. We shall use the following fact about bounded low-degree functions:

We give a high-level overview of how we are able to improve upon the bound of $\epsilon$ using the fact that the block sensitivity of a bounded low degree function is small. At one point in their proof, [7] lower bounds the probability of a linear form of Rademacher random variables $l(x_1,x_2,\mathrm{\cdots },x_t)=a_1{x}_1+\mathrm{\cdots }+a_t{x}_t$ exceeding a certain threshold times its standard deviation, i.e.,

(In the proof, $l(x_1,\mathrm{\cdots },x_t)$ is the linear part of a restriction of $f$: ${\displaystyle \sum _{j\in U}}{\widehat{f}}_j(U)x_j$ for some $U\subseteq [n]$.)

For each such point $x$ where this linear form is high, [7] shows that many related points $x^{\prime }$ must have $f(x^{\prime })>2$. (To be precise, these related points are obtained by applying an appropriate noise operator to $x$.) Using this they conclude that $f$ must deviate from the interval $[0,1]$ too often and therefore cannot be approximated by any bounded function.

We follow the proof of [7] up until this point. Instead of directly lower bounding the probability that $a_1{x}_1+\mathrm{\cdots }+a_t{x}_t$ is high, we partition the set of variables $[t]$ into $L$ blocks $B_1,\mathrm{\cdots },B_L$ ($L$ is an appropriately chosen parameter) such that each block gets roughly same total weight: for all $j\in [L],$

It will turn out that the $a_i$’s are sufficiently small for such a partition to exist. For each block we lower bound the probability that the linear form restricted to this block is high:

Now, on a random assignment $z$, the linear form restricted to many of these blocks will be high. Take such a block $B_i$: ${\displaystyle \sum _{j\in B_i}}{a}_j{z}_j\ge \tilde{\alpha }\sqrt{{\displaystyle \sum _{j\in B_i}}{a}_j^2}$. For each such block we will be able to find a large number of related points $z_i$ such that $|f(z)-f(z_i)|$ is large. (In our case, these related points are obtained by applying an appropriate noise operator restricted to $B_i$.) Crucially, these related points will differ from $z$ only at $B_i$. Thus, we will find many points which differ from $z$ at disjoint sets and whose $f$ differ from $z$ significantly. This will show that $f$ cannot be too close to a bounded low degree function, because those functions have low block sensitivity.

Our advantage is that we need to set ${\alpha }^{\prime }$ so that we can conclude $|f(z)-f(z^{\prime })|$ is only somewhat larger than $\mathrm{\Omega }(d^2/L)$ (as opposed to $\mathrm{\Omega }(1)$ in [7]) - by setting $L$ large enough this allows us to set a much smaller $\alpha$ and get rid of the quadratic exponential dependence.

In this section we compile some lemmas that we shall use in our proof.