Zoom link and password:

https://princeton.zoom.us/j/92251178129 

Password required

If f:{0,1}^n->{0,1} is an XOR of a subset of coordinates, then for any pair of inputs x,y it holds that f(x XOR y) = f(x) XOR f(y), and these are the only such functions. In fact, a robust version of the converse statement also holds: if f(x XOR y) = f(x) XOR f(y) for most inputs x,y, then f must be close to an XOR. This is the well-known "Linearity Testing" algorithm, a classical result in theoretical computer science. Does a similar result hold when XOR is replaced by other functions? We show that this is indeed the case for AND ("oligarchies"), with implications to judgment aggregation. This is part of a more general program, which also includes results such as Kalai's robust Arrow's theorem. Joint work with Yuval Filmus, Noam Lifshitz and Elchanan Mossel.