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, high–dimensional generalizations of these notions to 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 such notions of tensor rank and expansion in hypergraphs and their applications to algorithm design.

Our contributions are threefold. First, we give new applications of tensor rank to the area of parameterized and exact algorithms, unifying several prior algorithmic tools and obtaining faster, more space–efficient algorithms for a handful of problems. We then study algorithms for fast matrix multiplication. In this area we identify new limitations on current algorithmic approaches via connections to additive combinatorics and group theory. Finally, we give several new group–theoretic families of sparse spectral high–dimensional expanders.

140 pages

Thesis Committee:
Ryan O'Donnell (Chair)
Pravesh Kothari
Prasad Tetali
Alex Lubotzky (Weizmann Institute of Science)
Lawrence Paulson (University of Cambridge)

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

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu