Algorithmic Thresholds for Refuting Random Polynomial Systems

Consider a system of m polynomial equations { p i ( x ) = b i } i ≤ m of degree D ≥ 2 in n -dimensional variable x ∊ ℝ 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 ∊ ℕ, the ( n + m ) O ( d ) -time canonical sum-of-squares (SoS) relaxation refutes such a system with high probability whenever. 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 -time algorithms for all δ. Our upper-bound relies on establishing a sharp bound on the smallest integer d such that degree d – D polynomial combinations of the input p i s generate all degree- d polynomials in the ideal generated by the p i s. Our lower bound actually holds for the easier problem of distinguishing random polynomial systems as above from a distribution on polynomial systems with a “planted” solution. Our choice of planted distribution is slightly (and necessarily) subtle: it turns out that the natural and well-studied planted distribution for quadratic systems (studied as the matrix sensing problem in machine learning) is easily distinguishable whenever m ≥ Õ(n )–a factor n smaller than the threshold in our upper bound above. Thus, our setting provides an example where refutation is harder than search in the natural planted model.

Authors

• Jun-Ting Hsieh
• Pravesh K. Kothari

Keywords

No keywords are indexed for this paper.