AND testing and robust judgement aggregation

A function f ∶{0,1} n → {0,1} is called an approximate AND-homomorphism if choosing x , y ∈ n uniformly at random, we have that f ( x ∧ y ) = f ( x )∧ f ( y ) with probability at least 1−ε, where x ∧ y = ( x 1 ∧ y 1 ,…, x n ∧ y n ). We prove that if f ∶ {0,1} n → {0,1} is an approximate AND-homomorphism, then f is δ-close to either a constant function or an AND function, where δ(ε) → 0 as ε→ 0. This improves on a result of Nehama, who proved a similar statement in which δ depends on n . Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if f is ε-close to satisfying judgement aggregation, then it is δ(ε)-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama’s result, in which δ decays polynomially with n . Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation f = λ g , where is the downwards noise operator f ( x ) = y [ f ( x ∧ y )], f is [0,1]-valued, and g is {0,1}-valued. We identify all exact solutions to this equation, and show that any approximate solution in which f and λ g are close is close to an exact solution.

Authors

• Yuval Filmus
• Noam Lifshitz
• Dor Minzer
• Elchanan Mossel

Keywords

• Analysis of Boolean Functions
• Property Testing