When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
This work addresses theoretical problems in Boolean function analysis, offering refined conjectures that are incremental improvements over prior refutations.
The paper tackles two conjectures about Boolean functions involving the Majority function, refuting their original forms but providing nearly tight bounds on the noise parameter regimes where they hold for all n ≥ 5, with both conjectures holding for n=3.
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 Least Stable" (Benjamini et al., 1999) and the "Non-Interactive Correlation Distillation for Erasures" (Yang, 2004; O'Donnell and Wright, 2012). While both conjectures have been refuted in their originally stated form, we obtain a nearly tight characterization of the noise parameter regime in which each of the conjectures hold, for all $n \ge 5$. Whereas, for $n=3$, both conjectures hold in all noise parameter regimes. We state refined versions of both conjectures that we believe captures the spirit of the original conjectures.