Homomorphism Testing over Non-Abelian Groups

Title Of the Talk: “Homomorphism Testing over Non-Abelian Groups”
Speakers: Dr. Tushant Mittal (University of Chicago –> Stanford University)
Host Faculty: Dr. Nitin Saurabh
date: 2024-14-08 3:45pm–4:45pm

Abstract: Homomorphism testing is the problem of checking if a function between two groups is correlated with some homomorphism. Such tests are widely used in constructing probabilistically checkable proofs (PCPs) and many other areas of computer science.

In this talk, we will look at the setting of unitary-matrix valued functions on non-abelian groups. We will see what the famous Blum-Luby-Rubinfeld (BLR) test implies in this setup, and present our results on derandomizing this test.

Joint work with Sourya Roy.

directions of this line of work.

Speaker Profile:

Bio: Dr. Tushant Mittal is joining Stanford University as a Motwani Postdoctoral Fellow, following his recent graduation from the University of Chicago. Before his time at UChicago, he earned a B.Tech in Computer Science and Engineering from IIT Kanpur. His current research focuses on constructing structured pseudorandom objects, such as expanders, and analyzing their practical limits. More broadly, he is interested in applying algebraic techniques to solve computational problems.

Date:
2024-14-08 3:45pm–4:45pm

Venue
C-LH-9 s