29 problems

Let $\mathcal{P}$ be a binary-input memoryless symmetric (BMS) channel with output alphabet $\mathcal{Y}$, and let … be its capacity under the uniform input distribution. For a seq…

Almost optimal scaling-law conjecture. Reed–Muller codes have an almost optimal scaling-law over BSC channels under ML decoding.

Let $RM(r,m)$ denote the binary Reed–Muller code of order $r$, where $0\leq r\leq m$. A binary code is $\mathbb{Z}_4$-linear with respect to the Gray map if it is equivalent to the…

Let $RM(r,m)$ be the binary Reed–Muller code of length $2^m$, and let $C=RM(r,m)$ with $3\le r\le m-2$. Let $\phi$ denote the Gray map from quaternary words to binary words. Reed–M…

Small-parameter PMEPR lower-bound conjecture. At least for small values of $m$, the right-hand side is lower-bounded by

Let $RM(r,m)$ denote the Reed–Muller code of order $r$ in $m$ variables, and let its weight spectrum be the set of Hamming weights of its codewords. For a set $S$ of weights, write…

Let $\operatorname{WPRM}_d(w)$ denote the weighted projective Reed–Muller code of weighted degree $d$ over $\mathbb{F}_q$, where $w=(w_0,\dots,w_m)$ is the weight vector, and let…

Reed–Muller capacity conjecture. Reed–Muller codes achieve Shannon capacity on symmetric channels.

Let $m\geq 3$. For the binary lifted Reed–Muller code ${\mathrm{RM}}_2(1,m)(2|2^2)$, let ${\mathbb{D}}_{3\times 2^{m-2}}({\mathrm{RM}}_2(1,m)(2|2^2))$ denote the design whose block…

Construction 2 weight-spectrum conjecture. The set $S$ contains all weights in the two families

KasamiCarlet weight-spectrum conjecture. For any positive integer $c$ and $m\ge 2c$, the weight spectrum of $RM(m-c,m)$ is of the form

Automorphism-group conjecture. For $q>r>\frac{n(n-1)}{2}$, the automorphism group of $SRM_q[n,r]$ contains a subgroup isomorphic to $M$; equivalently, $SRM_q[n,r]$ is invariant und…

Let $\mathbf{V}$ be a dynamic freezing constraint matrix for a Reed–Muller code, and let $\pi$ be a permutation of the code coordinates. Write $\mathsf{BLTA}(n-1,1)$ for the block…

Let $RM(m-c,m)$ denote the binary Reed–Muller code of order $m-c$ in $m$ variables, and let its weight spectrum be the set of Hamming weights of its codewords. For a set of weights…

Let $n=2^m$, let $\mathbf{G}_{n}^{\operatorname{RM}}$ be the Reed–Muller generator matrix, and consider the successive decoder for the associated code construction. The message bit…

Let polar codes and Reed–Muller (RM) codes be code families whose generator matrices are formed from rows of the same square matrix. Both families achieve capacity on binary memory…

Reed–Muller (RM) codes are families of binary error-correcting codes obtained by evaluating Boolean polynomials of bounded degree on the Boolean cube. Their weight enumeration is t…

Let $m\ge 5$ be an integer, let $\alpha$ be a primitive element of ${\mathrm{GF}}(2^m)$, and let $g^*_{2,\alpha}(X)$ denote the generator polynomial of the shortened second-order R…

Metric regularity conjecture. All Reed–Muller codes are metrically regular.

Let $RM(2,n)$ and $RM(3,n)$ denote the binary Reed–Muller codes of orders $2$ and $3$, respectively. The cubic-function conjecture. The exact value of the maximum second-order nonl…

Hou's conjecture. The covering radius of $RM(2,7)$ is $40$.

Let $\mathrm{RM}_2(m,1)$ denote the binary Reed–Muller code of order $1$, and let $\mathrm{IC}_2(\mathrm{RM}_2(m,1))$ denote its incidence code. A PIR protocol is $t$-private if it…

A binary Reed–Muller code $\operatorname{RM}(n,v)$ has length $N=2^n$ and rate $R=\frac{1}{N}\sum_{i=0}^{v}\binom{n}{i}$. Transmission is considered over the binary erasure channel…

A binary Reed–Muller code $\operatorname{RM}(n,v)$ has length $N=2^n$ and rate $R=\frac{1}{N}\sum_{i=0}^{v}\binom{n}{i}$. Consider the sequence of rate-$1/2$ self-dual Reed–Muller…

Gopalan–Klivans–Zuckerman conjecture. For fixed $d$ and finite field $\mathbb{K}$,