Correlation bounds against polynomials

Paper

• Viola - Correlation bounds against polynomials

Correlation Bounds

• Notice that things like AND (which has large degree) easy correlation (the all zero polynomia).
• Cor_D(f,p) = $\lvert \Pr_{x\sim D}[f(x)=p(x)] - \Pr_{x\sim D}[f(x)\neq p(x)]\rvert$
• Cor_D(f,d) = $\max_p Cor_D(f,p)$.
• Open Question:
  • Is there an $f$ such that $Cor_D(f,\log n) \leq 1/\sqrt{n}$?
  • Notice that this is a hardness.
  • It asks for a hard $f$ that with $\log n$ degree can only be barely simulated.
  • A negative answer to this would imply that NP circuits have quasi polynomial size (non-trivial but easy with right techniques).
  • Notice that this says nothing about how easy the polynomial is to compute (algebraic sense) or how many monomials it has.
  • This question also related to number-on-forehead communication complexity.
• Algebrazation is not a barrier because of non-uniformity.

Bound 1: degree >> $\log n$ but correlation $\epsilon$ >> $1/n$

• $Cor_U(Maj,d) \leq O(d/\sqrt{n})$.
• $Cor(Maj,d) \geq O(d^2/n)$
• $Cor(Maj,1) \leq O(1/n)$.
• Tight bounds on Cor(Maj,d) are not known (in cases $d\neq 1$).
• mod_3 is a candidate for small correlation.
• $Cor(mod_3,d) \leq O(d/\sqrt{n})$.
  • Proof:
    • Consider any set $X$ for which the polynomial computes $mod_3$ correctly.
    • Use this polynomial of degree $n/2+d$ to now represent any boolean function on $X$.
    • This gives a relation between the number of functions and the number of polynomials.
    • This gives the tradeoff between $\lvert X\rvert$ and $d$.
• Hardness Amplification:
  • Given an explicit function $f$ that has correlation $\epsilon$ of some class $C$, construct a related function on $C'$ with $n'\sim n$ and \epsilon' << \epsilon$.
  • Yao's xor lemma: $f'=f(x_1)+\dots + f(x_n)$.
  • Open Question: Does Yao's xor lemma hold for polynomials of degree $d\geq \log n$, i.e., $Cor(f,n^{1/3})\leq 1/3$, $Cor(f',\log n^2)\leq 1/n^2$.
  • Lemma: The correlation of two majority functions with constant degree polynomials is $\log^{O(1)}/n$.
    • This requires low degree polynomials!

Bound 2: degree << $\log n$ but correlation $<<1/\sqrt{n}$

• The Inner product function $\sum_{i} x_i x_{i+1}$ has correlation $Cor(IP,1) = 2^{-n/2}$.
• Generalized Inner Product function has just blocks of size $k$.
• For every $n,d$, $Cor(GIP_{d+1},d )\leq \exp(-\Omega(n/4^d d))$.
• $Cor_D(\mod_3,d) \leq \exp(-n/c^d)$. Here the distribution is a bit special.