Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.06590 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913013697609728 |
|---|---|
| author | Kamath, Pritish Kumar, Ravi Manurangsi, Pasin |
| author_facet | Kamath, Pritish Kumar, Ravi Manurangsi, Pasin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06590 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | When Majority Fails: Tight Bounds for Correlation Distillation Conjectures Kamath, Pritish Kumar, Ravi Manurangsi, Pasin Computational Complexity 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. |
| title | When Majority Fails: Tight Bounds for Correlation Distillation Conjectures |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2604.06590 |