Computer Science Thesis Proposal
In Person - Reddy Conference Room, Gates Hillman 4405
Ph.D. Student, Computer Science Department, Carnegie Mellon University
The Kikuchi Matrix Method: Algorithms for “Beyond Average-Case” CSPs
By now, it is well known that foundational algorithmic problems that are notoriously hard in the worst-case become surprisingly tractable when the instances are chosen from certain natural probabilistic models. However, such algorithms for average-case inputs typically rely on rather brittle properties of the chosen probabilistic model and tend to break down even when the model is only slightly perturbed. The main motivation of this thesis is to find robust new algorithmic techniques that give algorithms for hybrids of worst-case and average-case input models that, on the one hand, avoid worst-case hardness, while at the same time do not overfit to a specific probabilistic model. In this thesis, we focus on the NP-complete problem of constraint satisfaction for semi-random and smoothed input models. We give new robust algorithms for constraint satisfaction in such models with the same algorithmic guarantees and thresholds as the best-known algorithms for the well-studied and idealized setting of fully random inputs.
The key technical ingredient underpinning our algorithms is a new class of spectral methods based on “Kikuchi matrices” built from hypergraphs associated with the input instance of a constraint satisfaction problem. Our algorithms and spectral techniques additionally have interesting consequences to well-studied problems in coding theory, cryptography, and extremal combinatorics.
Venkatesan Guruswami (Co-Chair, CMU/University of California, Berkeley)
Pravesh K. Kothari (Co-Chair)
Uriel Feige (Weizmann Institute)