Streaming MaxCut Section 5 Proof Technique
April 27, 2025
- Let Alice’s input \(x \in
\{0,1\}^n\) be drawn from a distribution designed to be hard
for the task
- Bob receives input \(M, w\) and
Alice’s \(c\)-bit message
- Argue that any protocol with communication \(c\) and advantage \(\delta\) must satisfy \(c = \Omega(\delta \sqrt{n})\).
- By Yao’s minimax principle, we can assume that
Alice and Bob are deterministic and analyze their performance on a
fixed hard distribution.
We can claim that Alice calculates the message deterministically
by Yao’s minimax principle. Informally the
principle states that to prove a lower bound against randomized
algorithms, it suffices to analyze a hard input
distribution. We can fix the worst-case randomness and analyze
the protocol as deterministic over a specially chosen input
distribution.
- Alice’s message function \(P :
\{0,1\}^n \to \{0,1\}^c\) induces a partition of the input
space into \(2^c\) parts: \[
A_i = \{ x \in \{0,1\}^n : P(x) = i \}
\]
- Since \(2^c\) is small, a
simple counting argument implies that many inputs must lie in
large partitions. Let \(A\) be one such large part
- The protocol must distinguish between two distributions over
Bob’s input:\[w \sim Mx \quad \text{vs.}
\quad w \sim \mathcal{U}(\{0,1\}^r)\] where \(x\) is uniformly sampled from a fixed
large partition \(A\) and \(M\) is a fixed matrix.
3. Fourier
Analysis of the Conditioned Distribution
- We study distribution of \(Mx\)
where \(x\) is uniformly random in
the fixed large parition
- Let \(p_M(z)=\Pr_{x\in A}[M x = z] =
\frac{|\{ x \in A: Mx = z \}|}{|A|}\)
- In other words \(p_{M}(z)\) is
the distribution for \(x \in A \in
\{0,1\}^c\)
- Next we aim to prove that \(p_{M}(z)\) is close to uniform
by bounding fourier mass weight coefficients of \(p_{M}(z)\) (this is just application of
definition looks easy)
- Using the previous we can calculate the total variational
distance \(||p_{M} -
U_{r}||_{tvd}^2\) by using Parsevals theorem
- We can set distance from uniform function \(g(z) = p_{M}(x)-\frac{1}{2^c}\), so
\(||p_{M} - U_{r}||_{tvd} = \sum_{x}
|g(z)|\)
Parseval theorem states that for any \(f: \{ 0,1 \}^n \to \mathbb{R}\): \[\mathbb{E}_{x \sim \{ 0,1 \}^n}[f(x)^2] =
\sum_{v \in \{ 0,1 \}^n} \widehat{f}(v)^2\] Note: if \(f\) is defined on \(\{ -1,1 \}^n\), then the corresponding
function defined on \(\{ 0,1 \}^n\)
is simply \(f_{01}(x_{1}, x_{2}, \ldots,
x_{n}) = f((-1)^{x_{1}}, (-1)^{x_{2}}, \ldots,
(-1)^{x_{n}})\).
4.
Bounding Fourier Spectrum via Representation Counting
- For a function \(f\) the
fourier coefficients \(\widehat{f}(v)\) measure how much \(f\) correlates with \((-1)^{x \cdot v}\)
- Distance of \(p_{M}\) to
uniformity si bounded by \(l_{2}\)
notm of part of the fourier spectrum of \(f\)
- Specifically each fourier coefficient \(\widehat{f}(v)\) we bound the number of
ways of representing \(v \in \{ 0,1
\}^n\) as \(M^T s\) where
\(s \in \{ 0,1 \}^r\) as \[\mathbb{E}_{M}[\#\{ s: M^T s = v \}] \leq
\text{ some suitable bound }\]
- This limits the influence of any single Fourier character,
allowing us to bound the total Fourier mass and thus the deviation
from uniform.
- Eventually we derive: \(\mathbb{E}_M
\left[ \|p_M - \mathcal{U}_r\|_{\mathrm{tvd}}^2 \right] =
\mathcal{O}(\text{small})\) in this paper the proof is
specific to the distribution of the hard graph distribution
5. Use TVD to
Derive Communication Lower Bound
- Total variation distance obeys: \[
\| (X, Y^1) - (X, Y^2) \|_{\mathrm{tvd}} = \mathbb{E}_{X}[\| Y^1_X -
Y^2_X \|_{\mathrm{tvd}}]
\]
- We establish distributions \(D^1,
D^2\) depending on Yes or No instance of the problem and show
that they are hard to distinguish with messages of length \(\mathcal{o}(\sqrt{ n })\)
- The protocol’s advantage implies a gap between \(D^1\) and \(D^2\), but we’ve shown that conditioned
on Alice’s message, this gap is small unless \(c = \Omega(\sqrt{n})\).
- By showing \(||D^1 - D^2||_{tvd} =
\mathcal{O}(\text{ something small })\), we prove
low-communication protocols cannot distinguish D-BHP