Peter Manohar

New Spectral Techniques in Algorithms, Combinatorics, and Coding Theory: The Kikuchi Matrix Method

Degree Type: Ph.D. in Computer Science
Advisor(s): Venkatesan Guruswami, Pravesh K. Kothari
Graduated: August 2024

Keywords: Spectral Methods, Constraint Satisfaction Problems, Locally Decodable Codes

Abstract

In this thesis, we present a new method to solve algorithmic and combinatorial problems by (1) reducing them to bounding the maximum, over x ∈ {-1,1}n, of homogeneous degree-q multilinear polynomials, and then (2) bounding the maximum value attained by these polynomials by analyzing the spectral properties of appropriately chosen induced subgraphs of Cayley graphs on the hypercube (and related variants) called "Kikuchi matrices".

We will present the following applications of this method.

  1. Designing algorithms for refuting/solving semirandom and smoothed instances of constraint satisfaction problems;
  2. Proving Feige's conjectured hypergraph Moore bound on the extremal girth vs. density trade-off for hypergraphs;
  3. Proving a cubic lower bound for 3-query locally decodable codes and an exponential lower bound for 3-query locally correctable codes.

Thesis Committee

Venkatesan Guruswami (Co-Chair, CMU/University of California, Berkeley)
Pravesh K. Kothari (Co-Chair, CMU/Institute for Advanced Study and Princeton University)
Ryan O'Donnell
Uriel Feige (Weizmann Institute)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Thesis Document

CMU-CS-24-142.pdf (2.26 MB) (242 pages)