% =====================================================================
%  CONJURA CONJECTURE STATEMENT
%  Blasiok-Lou-Rosen-Sudan's Conjecture 14: Reed-Muller codes
%  efficiently achieve capacity for the binary erasure channel.
%  Requires conjura-conjecture.cls in the same directory.
% =====================================================================
\documentclass{conjura-conjecture}

\runninghead{REED-MULLER CODES EFFICIENTLY ACHIEVE CAPACITY FOR BEC}

\newcommand{\Om}{\Omega}
\newcommand{\eps}{\varepsilon}
\newcommand{\F}{\mathbb{F}}
\newcommand{\RM}{\mathrm{RM}}
\newcommand{\Ber}{\mathsf{Ber}}

\begin{document}

\cjkicker{CONJURA \textperiodcentered{} OPEN PROBLEM}
\cjtitle{Reed-Muller Codes Efficiently Achieve Capacity for the Binary
  Erasure Channel}
\cjsubtitle{Capacity is known; the rate of convergence to it is not}
\cjstatus{Statement: AI-written from Jaros\l{}aw B\l{}asiok, Paul Lou,
  Alon Rosen and Madhu Sudan, \emph{Expanders Meet Reed-Muller: Easy
  Instances of Noisy k-XOR}, IACR ePrint 2026/664. Not yet checked by a
  human. This is their Conjecture 14. That Reed-Muller codes achieve
  capacity for the BEC is a theorem of Kudekar et al.; what is open is
  the \emph{gap to capacity} --- a polynomial rate of convergence. The
  source needs it to strengthen its refutation of the expansion-implies-hardness
  conjecture for noisy k-XOR from quasi-polynomially many constraints to
  polynomially many, and notes the question was raised explicitly in
  three prior works.}
\cjcategory{\emph{Coding Theory}.}

\vspace{0.4em}

\begin{informalconjecture}
Reed-Muller codes are the oldest family in coding theory and, it turns
out, among the best: they achieve capacity on the binary erasure channel,
which was proved only in 2016. Achieving capacity in the limit is not the
same as reaching it fast, though, and for an explicit code with an
efficient decoder the rate of convergence is much harder to control than
the limit. For random codes it is easy --- the gap closes like the inverse
square root of the blocklength. The conjecture is that Reed-Muller codes
do something of the same order: a gap to capacity that shrinks
polynomially in the blocklength.
\end{informalconjecture}

\section{The setting}\label{sec:setting}

Write $\RM(m,r)$ for the Reed-Muller code of order $r$ in $m$ variables:
the evaluations on $\F_{2}^{m}$ of polynomials in $\F_{2}[X]$ of total
degree at most $r$, a code of blocklength $M = 2^{m}$. Over the binary
erasure channel each coordinate is erased independently with probability
$\eta$, and the question is for which $\eta$ the erased codeword is still
recoverable with probability $1 - o(1)$.

Kudekar, Kumar, Mondelli, Pfister, \c{S}a\c{s}o\u{g}lu and Urbanke proved
that Reed-Muller codes achieve capacity over the BEC\@, recovering from
erasure rate $\eps - o_{M}(1)$, where $\eps := 1 - \mathrm{Rate}$. That
settles the limit. It does not say how fast the $o_{M}(1)$ term vanishes,
and it is exactly that rate --- the \emph{scaling exponent} --- which the
source needs and which is open.

For calibration, the source records what is known elsewhere. For random
codes this behaviour is true and relatively simple to show, with scaling
exponent $1/\gamma = 2$. For explicit codes with efficient decoding it is
much harder: the breakthrough results of Guruswami and Xing, and of
Hassani, Alishahi and Urbanke, showed that polar codes efficiently achieve
capacity for binary symmetric channels, i.e.\ have finite scaling
exponent, and variants of polar codes can achieve $1/\gamma \to 2$. For
Reed-Muller codes nothing of the kind is known.

\section{Notation and parameters}\label{sec:notation}

\begin{itemize}[nosep]
  \item $m$ is the number of variables, $r$ the order, $M = 2^{m}$ the
    blocklength of $\RM(m,r)$.
  \item $\eps := 1 - \mathrm{Rate}$; the code has rate at most
    $1 - \eps$.
  \item $\eta$ is the erasure probability; the erasure pattern is
    sampled from $\Ber(\eta)^{2^{m}}$.
  \item $\gamma$ is the constant the conjecture asserts exists;
    $1/\gamma$ is the scaling exponent.
\end{itemize}

\section{The conjecture}\label{sec:conjectures}

\begin{conjecture}[Reed-Muller codes efficiently achieve capacity for
  BEC, {\cite[Conjecture 14]{BLRS26}}]\label{conj:main}
There exists a constant $\gamma$ such that for every $m, r \in
\mathbb{N}$ for which $\RM(m,r)$ has rate at most $1 - \eps$, a random
erasure pattern sampled from $\Ber(\eta)^{2^{m}}$ is recoverable with
probability $1 - o(1)$ provided that
\[
  \eta \;<\; \eps - \frac{1}{M^{\gamma}},
\]
where $M = 2^{m}$ is the blocklength of the underlying code.
\end{conjecture}

\begin{remark}[An equivalent purely algebraic form]\label{rem:algebraic}
The source supplies one, and it is the cleanest way to attack or refute
the conjecture. Consider the linear space $\F_{2}[X]_{\le r}$ of
low-degree polynomials with dimension $(1-\eps)M$, and a random subset
$S$ of $(1-\eps)M + M^{1-\gamma}$ locations on the hypercube
$\F_{2}^{m}$. Conjecture~\ref{conj:main} is equivalent to the statement
that with probability $1 - o(1)$ there is no non-zero polynomial in
$\F_{2}[X]_{\le r}$ that vanishes on all points of $S$. So the question
is about how many random hypercube points are needed before they force a
low-degree polynomial to be zero --- a statement with no channel and no
decoder in it.
\end{remark}

\begin{remark}[The weaker form that already suffices]\label{rem:weak}
The source offers a second conjecture, which it describes as ``plausibly
simpler-to-prove'' and which is enough for its application.

\emph{Conjecture 16 (Weak Random Erasure Recovery).} There exist
constants $\gamma > 0$ and $\zeta \ge 1$ such that for every $m, r \in
\mathbb{N}$, if $\RM(m,r)$ has rate at most $1 - \eps$ for
$M^{-\gamma} < \eps < 1/2$, a random erasure pattern sampled from
$\Ber(\eta)^{2^{m}}$ is recoverable with probability $1 - o(1)$ provided
that $\eta < \eps^{\zeta}$.

The source states that Conjecture 16 is implied by
Conjecture~\ref{conj:main}, and proves its Main Theorem 2 assuming only
Conjecture 16. Anyone attacking this should attack the weaker one first;
a resolution should say which it settles, since they are not equivalent
as far as the source claims.
\end{remark}

\begin{remark}[What it buys, and what is already
  unconditional]\label{rem:payoff}
The source refutes the widely-held conjecture that expansion of the
constraint graph implies hardness of noisy $k$-XOR\@. Its Main Theorem 1 is
unconditional: for every constant $\alpha > 0$ there is an infinite
family of $k$-left-regular constraint graphs with
$M = 2^{\Theta(\log^{2} N)}$, $k = (\log N)^{\Theta(1/\alpha)}$, which is
$(N^{1-\alpha}, 1-o(1))$-expanding and on which the $\eta$-noisy $k$-XOR
distinguishing problem is solvable in time $\mathrm{poly}(M)$ at constant
noise rate $\eta = 1/3$.

Under Conjecture 16 --- hence under Conjecture~\ref{conj:main} --- the
source's Main Theorem 2 upgrades this to $M = N^{\Theta(1)}$, i.e.\ the
number of constraints polynomially related to the number of variables
rather than quasi-polynomially, at noise rate $\eta = N^{-c}$ for any $c
> 0$. The source's own summary: ``To get a result for a polynomial number
of equations in the number of variables we need much faster rate of
convergence to capacity than is currently known.''

So the refutation does not depend on this conjecture; only its strongest
form does.
\end{remark}

\begin{remark}[Not the source's own question]\label{rem:attribution}
The source records that ``[t]he question of the gap-to-capacity results
for RM codes for symmetric channels has been explicitly raised in [AY19,
Section V], [Has+18; MHU14], and in [ASY21].'' It is a coding-theory
question that the source imports and gives a new consequence to. A
resolution belongs to that older line.
\end{remark}

\begin{remark}[A separate question the source leaves
  open]\label{rem:neighbour}
Its construction needs the constraint graph to be an expander, which it
gets from the explicit lossless expanders of Guruswami, Umans and Vadhan
reinterpreted as coset graphs. The natural alternative --- random subspaces
--- it cannot analyse: ``we leave open the question of whether a random
subspace construction of coset graphs is expanding.'' That is a different
question and it is not this statement.
\end{remark}

\section{Bibliography}

\begin{conjurabibliography}{99}

\bibitem[BLRS26]{BLRS26}
Jaros\l{}aw B\l{}asiok, Paul Lou, Alon Rosen and Madhu Sudan.
\emph{Expanders meet Reed-Muller: easy instances of noisy $k$-XOR}.
IACR ePrint 2026/664.
The source. Conjecture 14, Remark 15 and Conjecture 16 are all on
page 9; Main Theorems 1 and 2 are stated informally in Section 1.3 and
proved as Theorems 37 and 38 in Section 6.

\bibitem[Kud+16]{Kud16}
Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D.\ Pfister,
Eren \c{S}a\c{s}o\u{g}lu and R\"udiger Urbanke.
\emph{Reed-Muller codes achieve capacity on erasure channels}.
STOC 2016.
The theorem that Reed-Muller codes achieve capacity over the BEC, whose
rate of convergence this conjecture is about. [UNVERIFIED] --- cited in
the source as [Kud+16]; the venue here is inferred.

\bibitem[GUV09]{GUV09}
Venkatesan Guruswami, Christopher Umans and Salil Vadhan.
\emph{Unbalanced expanders and randomness extractors from
Parvaresh-Vardy codes}.
Journal of the ACM, 2009.
The lossless expanders the source reinterprets as coset graphs, which is
what lets it obtain expansion while retaining Reed-Muller decoding.

\bibitem[GX15]{GX15}
Venkatesan Guruswami and Chaoping Xing.
\emph{Optimal rate list decoding over bounded alphabets using algebraic-geometric
codes}.
Cited by the source, with Hassani et al., for polar codes efficiently
achieving capacity for binary symmetric channels --- the comparison point
for what is wanted here. [UNVERIFIED] --- cited in the source as [GX15];
the bibliographic detail here is inferred and may name the wrong paper by
these authors.

\bibitem[Ale03]{Ale03}
Michael Alekhnovich.
\emph{More on average case vs approximation complexity}.
FOCS 2003.
The origin of the belief that expansion implies hardness for noisy
$k$-XOR, which the source refutes, and the source of the
inverse-polynomial noise-rate regime.

\end{conjurabibliography}

\end{document}
