Tushant Mittal: A General Framework for Low Soundess Homomorphism Testing
Автор: CMU Theory
Загружено: 2025-10-15
Просмотров: 34
CMU Theory Lunch Talk
Speaker: Tushant Mittal
Date: 10/15/2025
Title: A General Framework for Low Soundess Homomorphism Testing
Abstract:
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.
Доступные форматы для скачивания:
Скачать видео mp4
-
Информация по загрузке:
