Position: Ph.D. Student

Current Institution: UC Berkeley

Refuting random constraint satisfaction problems below the spectral threshold

The study of average-case instances of constraint satisfaction problems, such as 3SAT, sits at the intersection of many fields, from computer science to physics and combinatorics. The complexity-theoretic characterization of random 3SAT instances has consequences for many areas in computer science, most notably for cryptography.

Uniformly random instances of 3SAT are known to be unsatisfiable with high probability when there at least 5N clauses. However, given a random 3SAT instance on N variables, the task of refuting the instance, or of proving that the instance has no satisfying assignments, is hypothesized to be computationally hard if there are O(N) clauses–in fact, the best known algorithms for refutation require instances with at least Ω(N^{3/2}) clauses, a factor of N^{1/2} beyond the unsatisfiability threshold at O(N).

In this talk, I will describe a new spectral algorithm that refutes 3SAT instances with fewer clauses, given more time. Specifically, our algorithm refutes instances with Θ(N^{3/2 – delta/2}) clauses in exp(O(N^delta)) time, giving the same guarantees as the best known polynomial-time algorithms when delta = 0, and from there smoothly approaching the unsatisfiability threshold at delta = 1. Further, our algorithm strongly refutes the instances, certifying that no assignment satisfies more than a (1-epsilon)-fraction of constraints for a constant epsilon.

Our algorithms also imply tight upper bounds on the value of sum-of-squares relaxations for random CSPs, as well as the value of sum-of-squares relaxations for random polynomial maximization over the unit sphere (injective tensor norm).

Based on joint work with Prasad Raghavendra and Satish Rao.

Tselil Schramm is a 4th year PhD student in the UC Berkeley CS Theory group, with interests in spectral graph theory, spectral algorithms, approximation algorithms and semidefinite programming. She is advised by Prasad Raghavendra and Satish Rao, and supported by an NSF Graduate Research Fellowship and a UC Berkeley Chancellor’s Fellowship. She received her BS in Math/Computer Science at Harvey Mudd College. Her current research focus is understanding the performance of semidefinite programming hierarchies on average-case problems. Outside of research, she enjoys bouldering, hiking, backpacking, binge-watching shows on Netflix, and Yerba Mate tea.