Homomorphism testing over Non-Abelian groups

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.

Venue: A3 117, Vindhya

Speaker 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.