Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-075 | 22nd May 2022 07:04

Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes

RSS-Feed




Revision #1
Authors: Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan
Accepted on: 22nd May 2022 07:04
Downloads: 104
Keywords: 


Abstract:

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We show that, for $r \leq \gamma m$ (where $\gamma > 0$ is a small, absolute constant) and $k = (1-\epsilon) \cdot {m \choose {\leq r}}$ for any constant $\epsilon > 0$, the space of degree at most $r$ multilinear polynomials vanishing on a random set $Z = \{z_1,\ldots, z_k\}$ has dimension exactly ${m \choose {\leq r}} - k$ with probability $1 - o(1)$. This bound shows that random sets have a much smaller space of degree at most $r$ multilinear polynomials vanishing on them, compared to the worst-case bound (due to Wei (IEEE Trans. Inform. Theory, 1991)) of ${m \choose{\leq r}} - {{\log_2 k}\choose {\leq r}} \gg {m\choose{\leq r}} - k$.

Using this bound, we show that high-degree Reed-Muller codes ($\text{RM}(m,d)$ with $d > (1-\gamma) m$) ``achieve capacity'' under the Binary Erasure Channel in the sense that, for any $\epsilon > 0$, we can recover from $(1 - \epsilon) \cdot {m\choose {\leq m-d-1}}$ random erasures with probability $1 - o(1)$. This also implies that $\text{RM}(m,d)$ is also efficiently decodable from $\approx {m\choose {\leq m-(d/2)}}$ random errors for the same range of parameters.



Changes to previous version:

Fixed References


Paper:

TR22-075 | 21st May 2022 22:52

Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes


Abstract:

We study the following natural question on random sets of points in $\mathbb{F}_2^m$:

Given a random set of $k$ points $Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m$, what is the dimension of the space of degree at most $r$ multilinear polynomials that vanish on all points in $Z$?

We show that, for $r \leq \gamma m$ (where $\gamma > 0$ is a small, absolute constant) and $k = (1-\epsilon) \cdot {m \choose {\leq r}}$ for any constant $\epsilon > 0$, the space of degree at most $r$ multilinear polynomials vanishing on a random set $Z = \{z_1,\ldots, z_k\}$ has dimension exactly ${m \choose {\leq r}} - k$ with probability $1 - o(1)$. This bound shows that random sets have a much smaller space of degree at most $r$ multilinear polynomials vanishing on them, compared to the worst-case bound (due to Wei (IEEE Trans. Inform. Theory, 1991)) of ${m \choose{\leq r}} - {{\log_2 k}\choose {\leq r}} \gg {m\choose{\leq r}} - k$.

Using this bound, we show that high-degree Reed-Muller codes ($\text{RM}(m,d)$ with $d > (1-\gamma) m$) ``achieve capacity'' under the Binary Erasure Channel in the sense that, for any $\epsilon > 0$, we can recover from $(1 - \epsilon) \cdot {m\choose {\leq m-d-1}}$ random erasures with probability $1 - o(1)$. This also implies that $\text{RM}(m,d)$ is also efficiently decodable from $\approx {m\choose {\leq m-(d/2)}}$ random errors for the same range of parameters.



ISSN 1433-8092 | Imprint