ÍâÍøÌìÌÃ

Zoom link and password:

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.