Computer Science Thesis Oral
— 3:00pm
Location:
In Person
-
McWilliams Classroom, Gates Hillman 4303
Speaker:
KEVIN PRATT
,
Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://www.cs.cmu.edu/~kpratt/
Hypergraph Rank and Expansion
The linear-algebraic notions of matrix rank and expansion in graphs are ubiquitous throughout computer science, with applications to algebraic complexity theory, communication complexity, and derandomization. In recent years, however, higher-dimensional generalizations of these notions for tensors and hypergraphs have led to progress on a wide variety of problems, including the improved analysis of Markov chains, algorithms and barriers for fast matrix multiplication, and the discovery of good locally testable codes and quantum LDPC codes. Yet compared to their linear-algebraic counterparts, these notions are very poorly understood.
This thesis studies these notions of hypergraph rank and expansion, as well as their applications to algorithm design. We find new applications of tensor rank to the areas of parameterized and exact algorithms, unifying several prior approaches and obtaining faster, more space-efficient algorithms for several problems. We identify new limitations to current approaches to fast matrix multiplication via connections to additive/multiplicative combinatorics. On the topic of high-dimensional expansion, we find several new group-theoretic families of sparse local spectral high-dimensional expanders.
Thesis Committee:
Ryan O’Donnell (Chair)
Pravesh Kothari
Prasad Tetali
Alex Lubotzky (Weizmann Institute of Science)
Chris Uman (California Institute of Technology)