Seminars

View all Seminars  |  Download ICal for this event

Hypergraph expansion, CSPs, and algorithmic decoding of epsilon-balanced codes

Series: Theory Seminar

Speaker: Prof. Madhur Tulsiani, Associate Professor, Toyota Technological Institute at Chicago, Associate Professor (part time), Department of Computer Science, University of Chicago

Date/Time: Jun 16 21:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
We will discuss some new notions of hypergraph expansion, which can be exploited by spectral algorithms, as well as ones based on semidefinite programming hierarchies. These properties lead to new structural characterizations and algorithmic regularity lemmas for hypergraphs, as well as new decoding algorithms for codes based on bias-reduction via direct-sum, such as the breakthrough construction of epsilon-balanced codes by Ta-Shma. (Based on joint work with Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, and Shashank Srivastava)
<br>
<br>
For more details about the seminar please visit the website at Link
<br>
<br>
Microsoft Teams Link:
<br>
<a href="Link

Host Faculty: Sruthi Gorantla, Rahul Madhavan, and Rameesh Paul