Computer Science Thesis Proposal

— 3:00pm

Location:
In Person - Reddy Conference Room, Gates Hillman 4405

Speaker:
PETER MANOHAR, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.cs.cmu.edu/~pmanohar/

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.

Thesis Committee:

Venkatesan Guruswami (Co-Chair, CMU/University of California,  Berkeley)
Pravesh K. Kothari (Co-Chair)
Ryan O’Donnell
Uriel Feige (Weizmann Institute)

Add event to Google
Add event to iCal