When: Sunday, March 7,
10am
Where: Schreiber 309
Speaker: Yuval Filmus, Technion
Title:
Approximate Polymorphisms
A Boolean function f: {0,1}^n -> {0,1} is a polymorphism of XOR if f(x+y) = f(x)+f(y) for all x,y (addition is modulo 2). It is well-known that a function is a polymorphism of XOR iff it is an XOR of a subset of the coordinates. A celebrated result in theoretical computer science ("linearity testing") extends this to approximate polymorphisms of XOR: if f(x+y) = f(x)+f(y) for most x,y, then f is close to an exact polymorphism. We show that similar results hold for other functions, such as AND and Majority: approximate polymorphisms of AND are close to ANDs, and approximate polymorphisms of Majority essentially depend on a single coordinate.
Joint work with Noam Lifshitz (HUJI), Dor Minzer (MIT), and Elchanan Mossel (MIT).