Algorithmic Thresholds for Refuting Random Polynomial Systems

Jun Ting Hsieh, Pravesh K. Kothari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


Consider a system of m polynomial equations fpi(x) = bigi6m of degree D > 2 in n-dimensional variable x 2 Rn such that each coeficient of every pi and bis 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 eficient 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 2 N, the (n + m)O(d)-time canonical sum-of-squares (SoS) relaxation refutes such a system with high probability whenever m > O(n) ( n d )D1. We prove a lower bound in the restricted low-degree polynomial model of computation which suggests that this trade-o 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 & eO(n) n(1)(D1) for 2n -time algorithms for all. Our upper-bound relies on establishing a sharp bound on the smallest integer d such that degree dD polynomial combinations of the input pis generate all degree-d polynomials in the ideal generated by the pis. 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 > eO(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.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2022
PublisherAssociation for Computing Machinery
Number of pages50
ISBN (Electronic)9781611977073
StatePublished - 2022
Externally publishedYes
Event33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States
Duration: Jan 9 2022Jan 12 2022

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Conference33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Algorithmic Thresholds for Refuting Random Polynomial Systems'. Together they form a unique fingerprint.

Cite this