*********************************** * Princeton Discrete Math Seminar * *********************************** Speaker: Dor Minzer (IAS), Zoom link https://princeton.zoom.us/j/92251178129, password needed Thursday 16th April, 3:00. Title: Oligarchy testing 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. ---------------------------------- Next week: Stephan Thomasse Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)