Approximate Polymorphisms in Boolean Functions

Explore the concept of approximate polymorphisms in this 53-minute lecture by Yuval Filmus at the Hausdorff Center for Mathematics. Delve into the classical stability result known as linearity testing, which demonstrates that functions satisfying certain conditions for most inputs are close to an XOR of a subset of coordinates. Examine the implications of replacing the XOR operation with different operations and discover how stability still holds, albeit with some nuances. Learn about the proof techniques involving Jones' regularity lemma for Boolean functions and the It Ain't Over Till It's Over theorem. Gain insights from this joint work with Gilad Chase, Dor Minzer, Elchanan Mossel, and Nitin Saurabh, expanding your understanding of theoretical computer science and mathematical concepts.

Yuval Filmus: Approximate polymorphisms