Theory Lunch Seminar - Tushant Mittal October 15, 2025 12:00pm — 1:00pm Location: In Person - Gates Hillman 8102 Speaker: TUSHANT MITTAL , Motwani Postdoctoral Fellow, Department of Computer Science, Stanford University https://mittaltushant.com/ A General Framework for Low Soundness Homomorphism Testing Can one verify a proof just by reading a tiny part of it? If a function is linear on most small subsets, must it be close to a truly linear function? Such questions recur in theoretical computer science, and the goal is to define notions of approximate structure that are locally testable, and yet, let us deduce global structure. In this talk, I will present a general framework for defining efficiently testable notions of homomorphisms between groups, and prove an inverse result showing that such maps are close to genuine homomorphisms. This framework yields novel tests for a wide variety of groups in the low soundness (high error) regime, where very few results are known. Joint work with Sourya Roy, University of Iowa. For More Information: hfleisch@andrew.cmu.edu Add event to Google Add event to iCal
