Fourier Growth of Communication Protocols for XOR Functions

To evaluate the quantity $\sum_{i=1}^{n}\operatorname*{\mathbb{E}}[\mathcal{C}(\bm{x},\bm{y})\bm{x}_{i}\bm{y}_{i}]$, consider a random leaf $\bm{\ell}$ of the protocol and let $\bm{X}_{\bm{\ell}}\times\bm{Y}_{\bm{\ell}}$ be the corresponding rectangle. Since the leaf determines the answer of the protocol, denoted by $\mathcal{C}(\bm{\ell})$, the quantity above equals

where $\mu(\bm{X}_{\bm{\ell}})=\operatorname*{\mathbb{E}}\left[\bm{x}\,\middle|\,\bm{x}\in\bm{X}_{\bm{\ell}}\right]$ and $\mu(\bm{Y}_{\bm{\ell}})=\operatorname*{\mathbb{E}}\left[\bm{y}\,\middle|\,\bm{y}\in\bm{Y}_{\bm{\ell}}\right]$ are the center of masses of the rectangle. Our goal is to bound the magnitude of the random variable $\bm{z}=\left\langle\mu(\bm{X}_{\bm{\ell}}),\mu(\bm{Y}_{\bm{\ell}})\right\rangle$.

We shall show that $\operatorname*{\mathbb{E}}_{\bm{\ell}}[|\bm{z}|]\lesssim\sqrt{d}$. Note that $|\bm{z}|$ can be as large as $d$ in the worst case — for instance if the first $d$ coordinates of $\bm{X}_{\bm{\ell}}$ and $\bm{Y}_{\bm{\ell}}$ are fixed to the same value — thus we cannot argue for each leaf separately.

To analyze it for a random leaf, we first characterize the above as a martingale process using the tree structure of the protocol. The martingale process is defined as $\left(\bm{z}^{(t)}\right)_{t}$ where $\bm{z}^{(t)}:=\left\langle\mu(\bm{X}^{(t)}),\mu(\bm{Y}^{(t)})\right\rangle$ tracks the inner product between the center of masses $\mu(\bm{X}^{(t)})$ and $\mu(\bm{Y}^{(t)})$ of the current rectangle $\bm{X}^{(t)}\times\bm{Y}^{(t)}$ at step $t$. Denote the martingale differences by $\Delta\bm{z}^{(t+1)}=\bm{z}^{(t+1)}-\bm{z}^{(t)}$ and note that if in the $t^{\text{th}}$ step Alice sends a message, then

where $\Delta\mu(\bm{X}^{(t+1)})=\mu(\bm{X}^{(t+1)})-\mu(\bm{X}^{(t)})$ is the change in Alice’s center of mass. A similar expression holds if Bob sends a message. Then it suffices to bound the expected quadratic variation (see Section 3) since

where the equality holds due to the martingale property: $\operatorname*{\mathbb{E}}\left[\Delta\bm{z}^{(t+1)}\,\middle|\,\bm{z}^{(1)},\ldots\bm{z}^{(t)}\right]=0$.

To obtain the desired bound, we need to bound the expected quadratic variation by $O(d)$. Note that it could be the case that a single $\Delta\bm{z}^{(t+1)}$ scales like $\sqrt{d}$. For instance, if Bob first announces his first $d$ coordinates, $y_{1},\ldots,y_{d}$, and then Alice sends a majority of $x_{1}\cdot y_{1},\ldots,x_{d}\cdot y_{d}$, then in the last step Alice’s center of mass $\mu(\bm{X}^{(t+1)})$ changes by $\approx 1/\sqrt{d}$ in each of the first $d$ coordinates, and the inner product with Bob’s center of mass changes by $\approx\sqrt{d}$ in a single step.

Such cases make it difficult to directly control the individual step sizes of the martingale and we will only be able to obtain an amortized bound. It turns out, as we explain later, that such an amortized bound on the martingale can be obtained if Alice and Bob’s sets are not elongated in any direction. Therefore, we will transform the original protocol into a clean protocol by introducing real communication steps that slice the elongated directions. For this, it will be convenient to work in Gaussian space which also turns out to be essential in proving the optimal $O(\sqrt{d})$ bound.

A communication protocol in Gaussian space takes as inputs $\bm{x},\bm{y}\in\mathbb{R}^{n}$ where $\bm{x},\bm{y}$ are independently sampled from the Gaussian distribution $\gamma_{n}$. One can embed the original Boolean protocol in the Gaussian space by running the protocol on the uniformly distributed Boolean inputs $\mathrm{sgn}(\bm{x})$ and $\mathrm{sgn}(\bm{y})$ where $\mathrm{sgn}(\cdot)$ takes the sign of each coordinate. Note that any node of the protocol tree in the Gaussian space corresponds to a rectangle $X\times Y$ where $X,Y\subseteq\mathbb{R}^{n}$. Abusing the notation and defining their Gaussian centers of masses as $\mu(X)=\operatorname*{\mathbb{E}}_{\bm{x}\sim\gamma_{n}}\left[\bm{x}\,\middle|\,\bm{x}\in X\right]$ and $\mu(Y)=\operatorname*{\mathbb{E}}_{\bm{y}\sim\gamma_{n}}\left[\bm{y}\,\middle|\,\bm{y}\in Y\right]$, one can associate the same martingale $(\bm{z}^{(t)})_{t}$ with the protocol in the Gaussian space:

It turns out that bounding the quadratic variation of this martingale suffices to give a bound on $L_{1,2}(h)$ (see Section 4), so we will stick to the Gaussian setting. We now describe the ideas behind the cleanup process so that the step sizes can be controlled more easily.

The cleanup protocol runs the original protocol interspersed with some cleanup steps where Alice and Bob send real values. As outlined before, one of the goals of these cleanup steps is to ensure that the sets are not elongated in any direction, in order to control the martingale steps. In more detail, recall that we want to control

in the $t^{\text{th}}$ step where Alice speaks. There are two key underlying ideas for the cleanup steps:

• •

  Gram-Schmidt Orthogonalization: At each round, if the current rectangle is $\bm{X}\times\bm{Y}$, before Alice sends the actual message, she sends the inner product $\left\langle x,\mu({\bm{Y}})\right\rangle$ between her input and Bob’s current center of mass $\mu({\bm{Y}})$. This partitions Alice’s set $\bm{X}$ into affine slices orthogonal to Bob’s current center of mass $\mu(\bm{Y})$. Thus the change in Alice’s center of mass in later rounds is orthogonal to $\mu(\bm{Y})$ since it only takes place inside the affine slice.

  Recall that the martingale $\bm{z}^{(t)}$ is the inner product of Alice and Bob’s center of masses, and Bob’s center of mass does not change when Alice speaks. The original communication steps now do not contribute to the martingale and only the steps where the inner products are revealed do. In particular, if $t_{\mathrm{prev}}<t$ are two consecutive times where Alice revealed the inner product, then the change in Alice’s center of mass is orthogonal to change in Bob’s center of mass between time $t_{\mathrm{prev}}$ and $t$. Thus, conditioned on the rectangle $\bm{X}^{(t)}\times\bm{Y}^{(t)}$ fixed by the messages until time $t$, we have, by Jensen’s inequality,

  	$\displaystyle\operatorname*{\mathbb{E}}\left[(\Delta\bm{z}^{(t+1)})^{2}\,\middle|\,\bm{X}^{(t)},\bm{Y}^{(t)}\right]$	$\displaystyle=\operatorname*{\mathbb{E}}\left[\left\langle\Delta\mu(\bm{X}^{(t+1)}),\mu(\bm{Y}^{(t)})-\mu(\bm{Y}^{(t_{\mathrm{prev}})})\right\rangle^{2}\,\middle|\,\bm{X}^{(t)},\bm{Y}^{(t)}\right]$
  		$\displaystyle\leq\operatorname*{\mathbb{E}}\left[\left\langle\bm{x}-\mu(\bm{X}^{(t)}),\mu(\bm{Y}^{(t)})-\mu(\bm{Y}^{(t_{\mathrm{prev}})})\right\rangle^{2}\,\middle|\,\bm{X}^{(t)},\bm{Y}^{(t)}\right].$		(2.2)

  Note that the quantity on the right-hand side above is of the form $\left\langle\bm{x}-\operatorname*{\mathbb{E}}[\bm{x}],v\right\rangle$. In other words, it is the variance of the random vector $\bm{x}$ along direction $v$. To maintain a bound on this quantity, we introduce the notion of “not being elongated in any direction”.

• •

  Not elongated in any direction: We define the following notion to capture the fact that the random vector is not elongated in any direction: we say that a mean-zero random vector $\bm{x}^{\prime}=\bm{x}-\operatorname*{\mathbb{E}}[\bm{x}]$ in $\mathbb{R}^{n}$ is $\lambda$-pairwise clean, if for every $v\in\mathbb{R}^{n}$,

  $$\operatorname*{\mathbb{E}}\left[\left\langle\bm{x}^{\prime},v\right\rangle^{2}\right]\leq\lambda\cdot\|v\|^{2},$$

  (2.3)

  or equivalently, the operator norm of the covariance matrix $\operatorname*{\mathbb{E}}[\bm{x}^{\prime}\bm{x}^{\prime\top}]$ is at most $\lambda$. This can be considered a spectral notion of almost pairwise independence, since the pairwise moments are well-behaved in every direction.

If the input distribution conditioned on Alice’s set $\bm{X}^{(t)}$ is $O(1)$-pairwise clean, we say that her set is pairwise clean. Based on the above ideas, after Alice sends the initial message, if her set is not yet clean, she partitions it recursively by taking affine slices and transmitting real values. More precisely, while there is direction $\theta\in\mathbb{S}^{n-1}$ violating Equation 2.3, Alice does a cleanup of her set by sending the inner product $\left\langle x,\theta\right\rangle$. This direction is known to Bob as it only depends on Alice’s current space. In addition, this cleanup does not contribute to the martingale in the future because the inner product along this direction is fixed now.

The resulting protocol is pairwise clean in the sense that at each step⁶⁶6We remark that the sets are only clean at intermediate steps where a cleanup phase ends, but we show that because of the orthogonalization step, the other steps do not contribute to the value of the martingale., Alice’s current set is pairwise clean. Similar arguments work for Bob.

Let $\bm{d}$ be the total number of communication rounds including all the cleanup steps. Then, by the above argument, and denoting by $(\bm{\tau}_{m})_{m}$ and $(\bm{\tau}^{\prime}_{m})_{m}$ the indices of the inner product steps for Alice and Bob, we can ultimately bound

where again, the last equality follows from the martingale property. The right hand side above can be bounded by the expected number of communication rounds $\operatorname*{\mathbb{E}}[\bm{d}]$ using the level-one inequality (see Theorem 3.1) — this inequality bounds the Euclidean norm of the center of mass of a set in terms of its Gaussian measure.

Since the original communication only consists of $d$ rounds, the analysis essentially reduces to bounding the expected number of cleanup steps by $O(d)$, which is technically the most involved part of the proof.

It is implicit in the previous works on the Gap-Hamming Problem [18, 67] that large sets are not elongated in many directions: if a set $X\subseteq\mathbb{R}^{n}$ has Gaussian measure $\approx 2^{-d}$, then for a random vector $\bm{x}$ sampled from $X$, there are at most $m\lesssim d$ orthogonal directions $\theta_{1},\ldots,\theta_{m}$ such that $\operatorname*{\mathbb{E}}[\left\langle\bm{x}^{\prime},\theta_{i}\right\rangle^{2}]\gtrsim 1$ where $\bm{x}^{\prime}=\bm{x}-\operatorname*{\mathbb{E}}[\bm{x}]$. This is a consequence of the fact that the expectation of $\bm{q}=\sum_{i=1}^{m}\left\langle\bm{x}^{\prime},\theta_{i}\right\rangle^{2}$ can be bounded by $O(d)$ provided that $X$ has measure $\approx 2^{-d}$.

The above argument suggests that maybe we can clean up the set $X$ along these $O(d)$ bad orthogonal directions. However this is not enough for our purposes: after taking an affine slice, the set may not be clean in a direction where it was clean before. Moreover, since the parties take turns to send messages and clean up, the bad directions will also depend on the entire history of the protocol, including the previous real and Boolean communication. This adaptivity makes the analysis more delicate and to prove the optimal bound we crucially utilize the rotational symmetry of the Gaussian distribution. Indeed, the fact that a large set is not elongated in many directions also holds even when we replace the Gaussian distribution with the uniform distribution on $\{\pm 1\}^{n}$, but it is unclear how to obtain an optimal level-one bound using the latter.

In the final protocol, since the parties only send Boolean bits and linear forms of their inputs, conditioned on the history of the martingale, one can still say what the distribution of the next cleanup $\left\langle\bm{x},\theta\right\rangle$ looks like, as the Gaussian distribution is well-behaved under linear projections. We then use martingale concentration and stopping time arguments to show that the expected number of cleanup steps is indeed bounded by $O(d)$ even if the cleanup is adaptive.

We make two remarks in passing: First, we can also prove the optimal level-one bound using information-theoretic ideas but they do not seem to generalize to the level-two setting, so we adopt the alternative concentration-based approach here and they are similar in spirit. Second, it is possible from our proof approach (in particular, the approach for level two described next) to derive a weaker upper bound of $\sqrt{d}\cdot\mathrm{polylog}(n)$ for the level one while directly working with the uniform distribution on the hypercube.

Similar to the case of level one, the level-two Fourier growth also has a martingale formulation. In particular, let $\bm{X}^{(t)}$ and $\bm{Y}^{(t)}$ be Alice and Bob’s sets at time $t$ as before and define $\sigma(\bm{X}^{(t)})=\operatorname*{\mathbb{E}}\left[\bm{x}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{x}\,\middle|\,\bm{x}\in\bm{X}^{(t)}\right],\sigma(\bm{Y}^{(t)})=\operatorname*{\mathbb{E}}\left[\bm{y}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{y}\,\middle|\,\bm{y}\in\bm{Y}^{(t)}\right]$ to be the $n\times n$ matrices that represent the level-two center of masses of the two sets. Here $\bm{x}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{y}$ denotes the tensor product $\bm{x}\otimes\bm{y}$ with the diagonal zeroed out.⁷⁷7Here $x\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}y$ is an $n\times n$ matrix. We will also interchangeably view $n\times n$ matrices as $n^{2}$-length vectors. To bound the level-two Fourier growth, it suffices to bound the expected quadratic variation of the martingale $\left(\bm{z}^{(t)}\right)_{t}$ defined by taking the inner product of the level-two center of masses $\bm{z}^{(t)}:=\left\langle\sigma(\bm{X}^{(t)}),\sigma(\bm{Y}^{(t)})\right\rangle$ where $\left\langle\cdot,\cdot\right\rangle$ is the inner product of two matrices viewed as vectors.

To this end, we again move to Gaussian space where the inputs $x,y\in\mathbb{R}^{n}$ and transform the protocol to a clean protocol. First, we need an analog of the Gram-Schmidt orthogonalization step — this is achieved in a natural way by Alice sending inner product $\left\langle x\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}x,\sigma(\bm{Y}^{(t)})\right\rangle$ with Bob’s level-two center of mass, and Bob does the same. Note that Alice and Bob are now exchanging values of quadratic polynomials in their inputs. Thus, to control the step sizes, we now need to control the second moment of quadratic forms which naturally motivates the following spectral analogue of $4$-wise independence.

We say a random vector $\bm{x}$ is $4$-wise clean with parameter $\lambda$ if the operator norm of the $n^{2}\times n^{2}$ covariance matrix

is at most $\lambda$ where we view $\bm{x}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{x}-\operatorname*{\mathbb{E}}[\bm{x}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{x}]$ as an $n^{2}$-dimensional vector. This is equivalent to saying that for any quadratic form $\left\langle M,\bm{x}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{x}\right\rangle$,

where $\left\|M\right\|$ denotes the Euclidean norm of $M$ when viewed as a vector. Thus, this allows us to control the second moment of any quadratic polynomial (and in particular, fourth moments of linear functions). We note that one can generalize the above spectral notion to $k$-wise independence in the natural way by looking at the covariance matrix of the tensor $\bm{x}^{\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}k}$.

We say a set is $4$-wise clean with parameter $\lambda$ if Equation 2.5 is preserved for all $M$ with zero diagonal⁸⁸8The requirement of zero diagonal is for analysis purposes only and can be assumed without loss of generality since $\bm{x}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{x}$ is zero diagonal anyway.. Combined with this notion, one can define the cleanup in an analogous way to the level-one cleanup: While there exists some $M\in\mathbb{R}^{n\times n}$ violating Equation 2.5, Alice sends the quadratic form $\left\langle x\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}x,M\right\rangle$ to Bob until her set is 4-wise clean with parameter $\lambda$.

The crux of the proof is to bound the number of cleanup steps which, together with a similar analysis as in the level-one case, gives us the desired bound. We show that $m\lesssim d$ cleanup steps suffice in expectation to make the sets $4$-wise clean for $\lambda\leq d\cdot\mathrm{polylog}(n)$. Analogous to Equation 2.1 and Subsection 2.1, this gives a bound of $d^{3}\cdot\mathrm{polylog}(n)$ on the expected quadratic variation and implies $L_{1,2}(h)\leq d^{3/2}\cdot\mathrm{polylog}(n)$.

Since the parties send values of quadratic forms now, the analysis here is significantly more involved compared to the level-one case, even after moving to the Gaussian setting, where one could previously use the fact that the Gaussian distribution behaves nicely under linear projections. We rely on a powerful generalization of the Hanson-Wright inequality to a Banach-space-valued setting due to Adamczak, Latała, and Meller [5]. This inequality gives a tail bound for sum of squares of quadratic forms: In particular if $M_{1},\ldots,M_{m}$ are matrices with zero diagonal which form an orthonormal set when viewed as $n^{2}$ dimensional vectors, then the random variable $\bm{q}=\sum_{i=1}^{m}\left\langle\bm{x}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{x},M_{i}\right\rangle^{2}$ satisfies $\operatorname*{\mathbf{Pr}}_{\bm{x}\sim\gamma_{n}}[\bm{q}\geq t]\leq e^{-\Omega(\sqrt{t})}$ for any $t\gtrsim m^{2}$ (see Theorem 3.3 for a precise statement). We remark that this tail bound relies on the orthogonality of the quadratic forms and is much sharper than, for example, the bound obtained from hypercontractivity or other standard polynomial concentration inequalities.

In our setting, the matrices are being chosen adaptively. In addition, the parties are sending quadratic forms in their inputs, and the distribution of the next $\left\langle\bm{x}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{x},M\right\rangle$ conditioned on the history is hard to determine, unlike the level-one case. To handle this, we replace the real communication with Boolean communication of finite precision $\pm 1/\mathrm{poly}(n)$. This means that whenever Alice wants to perform cleanup $\left\langle\bm{x}\otimes\bm{x},M\right\rangle$ for some $M$ known to both parties, she sends only $O(\log(n))$ bits. On the one hand, this modification is similar enough to the cleanup protocol with real messages so that most of the argument carries through. On the other hand, now the protocol is completely discrete, which allows us to condition on any particular transcript.

For intuition, assume we fix a transcript of $L=d+O(m\log(n))$ bits which has gone through $m$ cleanups. Typically, this transcript should capture $\approx 2^{-L}$ of the probability mass. More crucially, the matrices $M_{1},\ldots,M_{m}$ for the cleanups are also fixed along the transcript, and one can apply the aforementioned Hanson-Wright inequality on $\bm{q}=\sum_{i=1}^{m}\left\langle\bm{x}\overset{\mathchoice{\mathbin{{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}{\otimes}\bm{x},M_{i}\right\rangle^{2}$. Combining the two facts together, we can apply the non-adaptive tail bound above and then condition on obtaining such typical transcript. This shows $\operatorname*{\mathbb{E}}[\bm{q}]\leq d^{2}\cdot\mathrm{polylog}(n)$. However, each quadratic form comes from a violation of Equation 2.5 and contributes at least $\lambda$ to $\bm{q}$ in expectation. This implies that $\operatorname*{\mathbb{E}}[\bm{q}]\geq\lambda\cdot m$ and by taking $\lambda=d\cdot\mathrm{polylog}(n)$, we derive that the number of cleanup steps $m\lesssim d$. This shows that the level-two Fourier growth is $O((m+d)\cdot\sqrt{\lambda})=d^{3/2}\cdot\mathrm{polylog}(n)$ completing the proof.

Note that if we could take $\lambda=\mathrm{polylog}(n)$ while having the same number of cleanup steps $m=d\cdot\mathrm{polylog}(n)$, then we would obtain an optimal level-two bound of $d\cdot\mathrm{polylog}(n)$. However, it is not clear how to use current approach to show this. In Subsection 8.2, we identify examples showing the tightness of our current analysis and also discuss potential ways to circumvent the obstacles within.