Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

Communication Complexity

Dutta, Saxena, Thierauf - Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

Main Result

• We will only look at univariate polynomials.
• $f$ is computed by sum of $r$th power if $f=\sum_{i=1}^s c_i l_i^r$ where $l_i$ are polynomials.
• Support Union size is $\lvert \cup_{i=1}^s supp(l_i)$, here supp is the non-zero polynomials in $l_i$.
• We denote this measure by $U(f,r,s)$.
• $U(f,r,s)\geq \Omega(|supp(f)|^{1/r})$ by trivial counting argument.
• Let us study $f=(x+1)^d$.
  • For $s=1$, if $r | d$ then $U(f,r,s)\leq d/r +1$.
  • For $s=2$, $U(f,r,s)\geq d/r+1$ (Theorem 25).
  • For $s=r+1$ and any $d$, $U(f,r,r+1)\leq d/r+1$ (Lemma 21).
  • For $s\geq c(d+1)$, $c>r$ $U(f,r,s)\leq O(d^{1/r})$.
• Conjecture 1: $U(f,r,d^\delta) \geq d/r^{\delta'}$ for large enough $d$ and constants $\delta\leq 1 \leq \delta'$.
• Theorem 1: If Conjecture 1 holds then blackbox PIT is in P.
  • Proof Idea:
  • Construct a $k$-variate polynomial from $f$.
  • Show that the above polynomial is hard assuming Conjecture 1.
  • This hardness will translate to an efficient hitting set for VP.
  • Details:
    • The first part will use an inverse kronecker substitution.
    • $P(x_1,\dots,x_n) \rightarrow P(x^{(n+1)^0},\dots,x^{(n+1)^{k-1}})=f(x)$.
    • This map is a bijection between supp(P) and supp(f).
    • Now we prove that size(P)$>d^{1/\mu}$ for some constant $\mu>1$.
    • If $f$ would not have that size, then cut the circuit at a specific layer.
      • Convert it to $\sum\prod$ for the top and bottom layer.
      • Then we can write it as $\sum c_i g_i^r$ circuit with at most $d^{\delta}$ summands and support-union bounded by $d/r^{\delta'}$.
      • This would contradict Conjecture 1.
    • $r\geq 25$ is required because:
      • Support-union size $\binom{k+kn/2}{k}>(n+1)^k > d$ instead of $d/r^{\delta'}$.
      • This would not give a contradiction.
    • The polynomial $P$ is actually explicit.

Interesting things to know

• Fischer Formula:
  • $g=\prod_{i\in [m]} g_i$ can be written as $g=\sum_{i\in [2^m]} c_j h_j^m$ where $h_j\in span(g_i \mid i\in [m])$.