论文标题
几乎是reed - 毛刺代码达到随机错误的恒定速率
Almost-Reed--Muller Codes Achieve Constant Rates for Random Errors
论文作者
论文摘要
本文考虑了“ $δ$ - 最多的芦苇 - 毛刺代码”，即，除了$ d $的单个单位分数外，所有除$δ$分数外的线性代码所跨越。结果表明，对于任何$δ> 0 $和任何$ \ varepsilon> 0 $，都存在$δ$的家族 - 最多的芦苇 - 毛刺代码，可正确$ 1/2- \ varepsilon $随机错误，较高的可能性。对于精确的芦苇毛刺代码，类似的结果尚不清楚，代表了长期猜想的较弱版本，芦苇毛刺代码实现了随机错误的能力（Abbe-Shpilka-Wigderson STOC '15）。我们的方法是基于芦苇毛刺代码的最新极化结果，结合了组合方法，以在芦苇刺激码头之间建立不平等。
This paper considers '$δ$-almost Reed-Muller codes', i.e., linear codes spanned by evaluations of all but a $δ$ fraction of monomials of degree at most $d$. It is shown that for any $δ> 0$ and any $\varepsilon>0$, there exists a family of $δ$-almost Reed-Muller codes of constant rate that correct $1/2-\varepsilon$ fraction of random errors with high probability. For exact Reed-Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed-Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC '15). Our approach is based on the recent polarization result for Reed-Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed-Muller code entropies.
