In the Max k-SAT problem, the input consists of a collection of k-clauses—i.e., a disjunction of k literals (variables or their negations) over n variables—and the goal is to find an assignment that satisfies the largest possible fraction of these constraints. No sub-exponential (i.e., 2^{o(n)}) time algorithm with a non-trivial guarantee is known for the problem. In fact, such an algorithm is conjectured not to exist (Exponential Time Hypothesis, Impagliazzo and Paturi, 1999). Consequently, researchers explored natural probabilistic input models for k-SAT and related problems and developed algorithms with strong guarantees, albeit by relying heavily on specific input assumptions. 

 In 2006, Feige introduced the smoothed model of k-SAT, a hybrid of worst-case and probabilistic input models, hoping to find efficient algorithms with strong guarantees that minimized "overfitting" to a specific random model. 

In this talk, I will discuss an algorithm that obtains (conjecturally) optimal guarantees for Feige's model of k-SAT and related problems, the heart of which is a new family of spectral methods based on "Kikuchi" matrices. These methods have surprising applications to extremal combinatorics and coding theory, which I will focus on in the talk. These include the resolution (up to a logarithmic factor) of a certain girth vs. size trade-off for hypergraphs (the "hypergraph Moore bound") conjectured by Feige (2008), lower bounds for locally decodable and locally correctable codes, and very recently, improved lower bounds for data structures.

The talk is based on joint works with Jackson Abascal, Venkatesan Guruswami, Tim Hsieh, Peter Manohar, Sidhanth Mohnaty, David Munha-Correia, and Benny Sudakov.