Doctoral Thesis Proposal - Noah G. Singer

April 30, 2026  3:00PM—4:30PM

Location:
3002 - Newell-Simon Hall

Speaker:
NOAH G. SINGER, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://noahsinger.org/

Expansion of coset complexes and applications

In computer science and discrete mathematics, a hypergraph is a collection of subsets of a set of vertices; in particular, a graph is a collection of (unordered) pairs of vertices. Graphs are used to encode pairwise relationships between objects, and hypergraphs to encode more general multi-way relationships.

High-dimensional expanders are, informally, hypergraphs which are "well-connected" in a quantitative sense. While expansion in the "low-dimensional" case of graphs has been studied intensively since the 1970s, high-dimensional expanders have recently gained visibility for their role in a number of theoretical breakthroughs, such as the construction of efficient sampling algorithms for spanning trees (Anari–Liu–Oveis Gharan–Vinzant, STOC 2019, Ann. Math. 2024), optimal locally testable codes (Dinur–Evra–Livne–Lubotzky–Mozes, STOC 2022), and efficient low-soundness PCPs (Bafna–Minzer–Vyas, STOC 2025).

Kaufman and Oppenheim (STOC 2018, Eur. J. Comb. 2023) gave a remarkably simple construction of high-dimensional expanders by using carefully chosen groups of matrices to instantiate a classical construction known as a "coset complex". In this thesis, we further investigate the expansion of these complexes and various generalizations, as well as applications of this expansion in computer science and mathematics.

In two preliminary works (joint with Ryan O’Donnell), we:

  1. Investigated a particular notion of high-dimensional expansion ("1-cosystolic expansion") on certain generalized KO complexes by combining intricate group-theoretic arguments with computer-assisted matrix rank calculations.
  2. Showed that KO complexes have a "low-soundness agreement testing" property which allows them to be used inside the PCP of Bafna et al., replacing a much more complicated construction.

In this proposal, we propose several additional directions for the Ph.D. thesis. These include:

  1. Using the KO complex to improve the complexity of the Bafna et al. PCP (e.g., the verifier or prover runtimes),
  2. systematically characterizing the coboundary and cosystolic expansion of generalizations of KO complexes; and
  3. improving existing constructions of agreement testers by using alternative kinds of tests.

Thesis Committee:

Ryan O'Donnell (Chair)
Aayush Jain
Yang P. Liu
Irit Dinur (Institute for Advanced Study)
Madhur Tulsiani (Toyota Technological Institute at Chicago & University of Chicago)

Additional Information

Contact
Matt Stewart

Add event to Google
Add event to iCal