[Colloquium] U of C - CS Theory Seminar - November 12, 2024

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Siqi Liu, PhD
Institute for Advanced Study


[cid:image001.jpg at 01DB2F9A.ED9BC780]

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.



Bio: I am a postdoc at the Institute for Advanced Study. I got my PhD in Computer Science from UC Berkeley in 2023, advised by Alessandro Chiesa. I am interested in constructing expanding graphs and hypergraphs and applying them to build codes and proof systems.




Host: Aaron Potechin











-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241111/694d94e8/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 1030979 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241111/694d94e8/attachment-0001.jpg>