When Majority Fails: Tight Bounds for Correlation Distillation Conjectures

Pritish Kamath, Ravi Kumar, Pasin Manurangsi

We study two conjectures posed in the analysis of Boolean functions $f:\{-1,1{\}}^n\to \{-1,1\}$, in both of which, the Majority function plays a central role: the "Majority is…