## Abstract

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 language | English (US) |
---|---|

Title of host publication | ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 |

Publisher | Association for Computing Machinery |

Pages | 1154-1203 |

Number of pages | 50 |

ISBN (Electronic) | 9781611977073 |

State | Published - 2022 |

Externally published | Yes |

Event | 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States Duration: Jan 9 2022 → Jan 12 2022 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2022-January |

### Conference

Conference | 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 |
---|---|

Country/Territory | United States |

City | Alexander |

Period | 1/9/22 → 1/12/22 |

## All Science Journal Classification (ASJC) codes

- Software
- General Mathematics