Carnegie Mellon University
Browse
- No file added yet -

Hypergraph Rank and Expansion

Download (1.4 MB)
thesis
posted on 2023-09-27, 20:43 authored by Kevin PrattKevin Pratt

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. 

History

Date

2023-09-07

Degree Type

  • Dissertation

Department

  • Computer Science

Degree Name

  • Doctor of Philosophy (PhD)

Advisor(s)

Ryan O'Donnell

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC