Algorithmic Thresholds for Refuting Random Polynomial Systems

Jun-Ting Hsieh, Pravesh K. Kothari

Consider a system of $m$ polynomial equations $\{p_i(x)=b_i{\}}_{i\le m}$ of degree $D\ge 2$ in $n$-dimensional variable $x\in {\mathbb{R}}^n$ such that each coefficient of every…