[CS] Tushant Mittal Dissertation Defense/Jul 1, 2024

[via cs]

This is an announcement of Tushant Mittal's Dissertation Defense.
===============================================
Candidate: Tushant Mittal

Date: Monday, July 01, 2024

Time:  1 pm CT

Remote Location: https://uchicago.zoom.us/j/8537256311?pwd=QmxEVFhnNGp4WGxQSTkxZFdmOTNwZz09&omn=94501925934  Meeting ID: 853 725 6311 Passcode: 881565

Location: TTIC 530

Title: Expanders with Symmetries: Constructions and Applications

Abstract: Expanders are graphs with a magical property; they are very sparse yet extremely well-connected. The notion of expansion and the construction of expanders has led to significant developments in theoretical computer science. The ability to construct expanders with symmetries enables a host of new applications like quantum LDPC codes and classical locally testable codes. In this thesis, we give new constructions and applications of symmetric expanders.

This talk will focus on expanders with symmetries of non-Abelian groups. We will look at a generic amplification technique that takes a weak expander and constructs an almost optimal one while preserving symmetries. As an application of such graphs, we will see how symmetric expanders can be used to give a randomness-efficient algorithm for a fundamental problem, homomorphism testing. Here, one has query access to a function and has to decide whether the function is "close to" a homomorphism.

Advisors: Janos Simon and Madhur Tulsiani

Committee Members: Madhur Tulsiani, Bill Fefferman, Janos Simon, and Ryan O'Donnell