Algorithmic Thresholds for Refuting Random Polynomial Systems
March 16, 2022 (GHC 8102)

Abstract: Consider a system of $m$ polynomial equations $\{p_i(x)=b_i\}_{i \leq m}$ of degree $D \geq 2$ in $n$-dimensional variable $x\in \mathbb{R}^n$ such that each coefficient of every $p_i$ and $b_i$s are chosen at random and independently from some continuous distribution. We study the basic question of determining the smallest $m$ -- the algorithmic threshold -- for which efficient algorithms can find refutations (i.e. certificates of unsatisfiability) for such systems. This setting generalizes problems such as refuting random SAT instances, low-rank matrix sensing and certifying pseudo-randomness of Goldreich's candidate generators and generalizations.

We show that for every $d\in \mathbb{N}$, the $(n+m)^{O(d)}$-time canonical sum-of-squares (SoS) relaxation refutes such a system with high probability whenever $m \geq O(n)(n/d)^{D−1}$. We prove a lower bound in the restricted low-degree polynomial model of computation which suggests that this trade-off between SoS degree and the number of equations is nearly tight for all $d$. We also confirm the predictions of this lower bound in a limited setting by showing a lower bound on the canonical degree-4 sum-of-squares relaxation for refuting random quadratic polynomials. Together, our results provide evidence for an algorithmic threshold for the problem at $m \geq \tilde{O}(n)\cdot n^{(1−\delta)(D−1)}$ for $2^{n^\delta}$-time algorithms for all $\delta$.

This is joint work with Pravesh Kothari.