4
$\begingroup$

Does any one knows if there is a non-quantum proof of the fact that non-linear 2-query LDC must have exponential size?

$\endgroup$
4
$\begingroup$

Yes, there is. Ben-Aroya, Regev and de Wolf in "A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs" (FOCS '08) provide a non-quantum proof of the exponential lower bound for 2-query LDC's, although there are similarities between the quantum and non-quantum proof techniques.

Here's a rough sketch of their proof. Let $C: \{\pm 1\}^m \to \{\pm 1\}^n$ be a $2$-query LDC. Then, for a given $x \in \{0,1\}^m$, set $M(x)$ to be the rank-1 matrix whose $(i,j)$'th entry is $C(x)_i C(x)_j$. $M$ is a matrix-valued function, and we can look at its matrix-valued Fourier coefficients: $\widehat{M}(\alpha) = \sum_{x} M(x) \prod_{i \in \alpha} x_i$. But now, observe that $\widehat{M}(\{i\})$ computes the matrix whose $(j,k)$'th entry is the expected correlation of $x_i$ with $C(x)_j C(x)_k$. Thus, if $C$ is a $2$-query LDC, we know that for every $i \in [m]$, many entries in $\widehat{M}(\{i\})$ are larger than some $\epsilon$. This allows you to lowerbound the $p$-norm of $\widehat{M}(\{i\})$. Finally, you can then apply their matrix-valued hypercontractive inequality, which is the main theorem of the paper, to get a lowerbound on $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy