ECCC-Report TR22-075https://eccc.weizmann.ac.il/report/2022/075Comments and Revisions published for TR22-075en-usSun, 22 May 2022 07:04:47 +0300
Revision 1
| Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes |
Prahladh Harsha,
Siddharth Bhandari,
Srikanth Srinivasan,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2022/075#revision1We 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. Sun, 22 May 2022 07:04:47 +0300https://eccc.weizmann.ac.il/report/2022/075#revision1
Paper TR22-075
| Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes |
Prahladh Harsha,
Siddharth Bhandari,
Srikanth Srinivasan,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2022/075We 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. Sat, 21 May 2022 22:53:52 +0300https://eccc.weizmann.ac.il/report/2022/075