Sourya Roy (U of Iowa)- New Results in Homomorphism Testing

Abstract: The homomorphism testing problem plays a central role in a wide range of questions in theoretical computer science. Since the seminal linearity testing result of Blum, Luby, and Rubinfeld, it has been extensively studied in the literature. However, comparatively few results are known in the so-called “low soundness” regime. In this talk, I will present a general framework for designing homomorphism tests over finite groups in the low soundness setting. Using this framework, we prove several new constant-query testing results for various families of abelian and non-abelian groups. I will also briefly describe new results for linearity testing on the Boolean half-slice, including a three-query test whose parameters match those obtained by BLR on the entire hypercube. This talk is based on joint works with Tushant Mittal, Silas Richelson and Haakon Larsen.