[Theory] UC Theory Seminar

[Alexander Razborov via Theory]

Siqi Liu, PhD
IAS 
 
 

 
 Tuesday, November 12, 2024 at 3:30pm
Kent Chemical Laboratory, Room 102
 
 
Title:  Sparse spectral and coboundary high dimensional expanders
 
Abstract: High dimensional expanders (HDXs) are a class of expanding hypergraphs. Their importance is constantly growing with their roles in the breakthroughs in Markov chains [ALGV19], locally testable codes [DELLM22], and quantum codes [PP22, ABN23]. HDXs generalize the notion of expander graphs but differ from the latter in a couple ways. First, while various definitions of expansion are equivalent over graphs, they are different in hypergraphs, yielding different types of HDXs. Secondly, while sparse expanders are abundant in random graph models, bounded-degree HDXs seem to be rare in random hypergraph models. 
 
So far, the sparest random construction of HDXs comes from random geometric graphs (RGGs) [LMSY23]. In this talk we will introduce a deterministic construction of HDXs which can be viewed as a derandomization of the RGG construction. These hypergraphs are both spectral HDXs and coboundary HDXs. They are the sparsest known coboundary HDXs (over any group). In particular, their 1-skeletons are abelian Cayley graphs.
 
This is based on joint work with Yotam Dikstein and Avi Wigderson.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241107/cc252ec9/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 119658 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241107/cc252ec9/attachment-0001.jpg>