pith. sign in

arxiv: 2604.06590 · v1 · submitted 2026-04-08 · 💻 cs.CC

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures

Pritish Kamath , Ravi Kumar , Pasin Manurangsi This is my paper

Pith reviewed 2026-05-10 18:22 UTC · model grok-4.3

classification 💻 cs.CC
keywords boolean functionsmajority functionnoise stabilitycorrelation distillationconjecturesfourier analysiserasure channels
0
0 comments X

The pith

Two conjectures on Boolean functions hold for all noise levels when n equals 3, but only in restricted noise regimes when n is 5 or larger, with those regimes now tightly characterized.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper revisits two longstanding conjectures about Boolean functions f from n bits to a single bit, both of which assign a central role to the Majority function. The first conjecture asserts that Majority is the least stable under random noise; the second asserts that it achieves the best non-interactive correlation distillation under erasures. Although the original statements of both conjectures have already been disproved, the work shows that for three input bits the conjectures remain true no matter what the noise level is. For five or more bits it supplies nearly tight bounds on the noise parameters inside which each conjecture is valid and proposes refined versions of the conjectures that the authors believe recover the original intent.

Core claim

For n = 3 both the Majority-is-Least-Stable conjecture and the Non-Interactive Correlation Distillation conjecture hold for every noise parameter. For every n ≥ 5 the paper gives a nearly tight description of the noise intervals in which each conjecture is true and states refined versions of the conjectures that are expected to capture their intended meaning.

What carries the argument

The stability and correlation-distillation functionals of Boolean functions under independent bit-flip or erasure noise, with Majority singled out as the candidate extremal function.

If this is right

  • Refined statements now accurately predict the noise ranges in which Majority is extremal for stability and distillation.
  • For sufficiently small noise the original conjectures are restored as true statements.
  • The same thresholds separate regimes in which other Boolean functions can outperform Majority.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The refined conjectures can be checked computationally for moderate n to test whether they continue to hold.
  • The noise thresholds may determine when Majority-based protocols remain optimal in noisy communication settings.

Load-bearing premise

The analysis treats every possible Boolean function equally and models noise as independent random flips or erasures on each input bit.

What would settle it

An explicit Boolean function on five or more bits together with a concrete noise parameter outside the claimed interval that violates one of the refined conjectures would disprove the characterization.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper studies two conjectures in Boolean function analysis—the 'Majority is Least Stable' conjecture (Benjamini et al., 1999) and the 'Non-Interactive Correlation Distillation for Erasures' conjecture (Yang 2004; O'Donnell and Wright 2012)—both of which originally positioned the Majority function as extremal. It establishes a nearly tight characterization of the independent bit-flip noise parameter regimes in which each conjecture holds for all Boolean functions f:{-1,1}^n → {-1,1} when n ≥ 5, while proving both hold in every noise regime for n=3. Refined versions of the conjectures are stated separately as capturing the original intent.

Significance. If the stated upper and lower bounds are correct, the work supplies a precise delineation of the noise regimes where the original conjectures are valid, closing most of the gap left by prior refutations and fully resolving the n=3 case. This advances the understanding of noise stability and correlation distillation in the analysis of Boolean functions, with the matching bounds for n≥5 and the refined conjectures providing concrete, falsifiable statements for future work. The result is independent of fitted parameters and rests on standard noise models.

minor comments (1)
  1. The abstract states that refined conjectures 'capture the spirit' of the originals but does not elaborate on the precise sense in which they do so; a short paragraph in the introduction comparing the refined statements to the original formulations would improve clarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition that the work provides a precise delineation of the noise regimes for the conjectures and resolves the n=3 case. We appreciate the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives tight mathematical bounds characterizing noise-parameter regimes for two Boolean-function conjectures under independent bit-flip noise. For n=3 the claims hold universally; for n≥5 the upper and lower bounds are obtained via direct analysis of all f:{-1,1}^n→{-1,1} without parameter fitting, self-referential definitions, or load-bearing self-citations. The refined conjectures are presented separately as author beliefs and are not used in the characterization proofs. No step reduces by construction to its own inputs or renames a known result as a new derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, ad-hoc axioms, or invented entities; work rests on standard Fourier analysis and noise operators in Boolean function theory.

axioms (1)
  • standard math Standard properties of the noise operator and Fourier analysis on the hypercube
    Invoked implicitly to study stability and correlation distillation for Boolean functions.

pith-pipeline@v0.9.0 · 5451 in / 1169 out tokens · 107713 ms · 2026-05-10T18:22:42.029014+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Noise sensitivity of B oolean functions and applications to percolation

    Itai Benjamini, Gil Kalai, and Oded Schramm. Noise sensitivity of B oolean functions and applications to percolation. Publications Math \'e matiques de l'Institut des Hautes \'E tudes Scientifiques , 90 0 (1): 0 5--43, 1999

    work page 1999

  2. [2]

    On the ``Majority is Least Stable'' conjecture

    Aniruddha Biswas and Palash Sarkar. On the ``Majority is Least Stable'' conjecture . IPL, 179, 2023

    work page 2023

  3. [3]

    Noise stability is computable and approximately low-dimensional

    Anindya De, Elchanan Mossel, and Joe Neeman. Noise stability is computable and approximately low-dimensional. In CCC, pages 10:1--10:11, 2017

    work page 2017

  4. [4]

    Non interactive simulation of correlated distributions is decidable

    Anindya De, Elchanan Mossel, and Joe Neeman. Non interactive simulation of correlated distributions is decidable. In SODA, pages 2728--2746, 2018

    work page 2018

  5. [5]

    Heilman, Elchanan Mossel, Sushant Sachdeva, Andrew Wan, and Karl Wimmer

    Yuval Filmus, Hamed Hatami, Steven M. Heilman, Elchanan Mossel, Sushant Sachdeva, Andrew Wan, and Karl Wimmer. Real analysis in computer science: A collection of open problems, 2014. URL https://simons.berkeley.edu/sites/default/files/openprobsmerged.pdf

    work page 2014

  6. [6]

    Das statistische problem der korrelation als variations- und eigenwertproblem und sein zusammenhang mit der ausgleichsrechnung

    Hans Gebelein. Das statistische problem der korrelation als variations- und eigenwertproblem und sein zusammenhang mit der ausgleichsrechnung. J. Appl. Math. Mech, / Zeitschrift für Angewandte Mathematik und Mechanik (ZAMM), 21 0 (6): 0 364--379, 1941

    work page 1941

  7. [7]

    Decidability of non-interactive simulation of joint distributions

    Badih Ghazi, Pritish Kamath, and Madhu Sudan. Decidability of non-interactive simulation of joint distributions. In FOCS, pages 545--554, 2016

    work page 2016

  8. [8]

    Dimension reduction for polynomials over G aussian space and applications

    Badih Ghazi, Pritish Kamath, and Prasad Raghavendra. Dimension reduction for polynomials over G aussian space and applications. In CCC, pages 28:1--28:37, 2018

    work page 2018

  9. [9]

    Stability of linear threshold functions

    Sivakanth Gopi. Stability of linear threshold functions. Undergraduate thesis, IIT Bombay, 2013. URL https://gopisivakanth.github.io/files/UndergraduateThesis_IITBombay.pdf

    work page 2013

  10. [10]

    H. O. Hirschfeld. A connection between correlation and contingency. Math. Proc. Cambridge Phil. Soc., 31 0 (4): 0 520--524, 1935

    work page 1935

  11. [11]

    Ivanisvili, X

    Paata Ivanisvili and Xinyuan Xie. Counterexample to majority optimality in NICD with erasures. arXiv, 2510.20013, 2025

    work page arXiv 2025

  12. [12]

    A counterexample to the ``majority is least stable" conjecture

    Vishesh Jain. A counterexample to the ``majority is least stable" conjecture. arXiv, 1703.07657, 2017

    work page arXiv 2017

  13. [13]

    Gaussian bounds for noise correlation of functions

    Elchanan Mossel. Gaussian bounds for noise correlation of functions. GAFA, 19: 0 1713--1756, 2010

    work page 2010

  14. [14]

    Noise stability of functions with low influences: Invariance and optimality

    Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Ann. Math., 171 0 (1): 0 295--341, 2010

    work page 2010

  15. [15]

    Computational Applications Of Noise Sensitivity

    Ryan O'Donnell. Computational Applications Of Noise Sensitivity. PhD thesis, MIT, 2003

    work page 2003

  16. [16]

    Analysis of Boolean Functions

    Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 1st edition, 2014

    work page 2014

  17. [17]

    A new point of NP -hardness for unique games

    Ryan O'Donnell and John Wright. A new point of NP -hardness for unique games. In STOC, pages 289--306, 2012

    work page 2012

  18. [18]

    On measures of dependence

    Alfr \'e d R \'e nyi. On measures of dependence. Acta Mathematica Academiae Scientiarum Hungarica, 10: 0 441--451, 1959

    work page 1959

  19. [19]

    H. S. Witsenhausen. On sequences of pairs of dependent random variables. SIAM J. Appl. Math., 28 0 (1): 0 100--113, 1975

    work page 1975

  20. [20]

    On the (im)possibility of non-interactive correlation distillation

    Ke Yang. On the (im)possibility of non-interactive correlation distillation. In LATIN, pages 222--231, 2004

    work page 2004