2
$\begingroup$

In a paper on a proximity test for Reed-Solomon codes the authors state an "extremely optimistical" conjecture on the list decodability of Reed-Solomon codes (over prime fields $\mathbb F_q$) up to the capacity bound. Concretely, they state:

(Conjecture 21 in BGKS20) For every $\rho>0$, there is a constant $C_\rho$ such that every Reed-Solomon code (over $\mathbb F_q$) of length $n$ and rate $\rho$ is list-decodable from $1-\rho-\varepsilon$ fraction errors with list size bounded by $\left(\frac{n}{\varepsilon}\right)^{C_\rho}$.

As there is no discussion on the plausability of the conjecture in that paper, and I am not an expert in the theory of codes: What do experts think about this conjecture?

Some background: proximity tests for Reed-Solomon codes are one of the key components in recent constructions of succinct interactive proofs for general computations. Their soundness is proven up to the Johnson bound, but practitioners tend to use the above conjecture for efficiency reasons (it reduces the number of samples of the test significantly).

Improve this question
$\endgroup$
7
  • $\begingroup$ @JyrkiLahtonen Thanks for the reply. However, I am not sure if I fully understand your comment. A too brave conjecture? $\endgroup$
    – U. Haboeck
    Commented Sep 3, 2022 at 9:08
  • $\begingroup$ Sorry. I deleted only my main comment making the remaining one incomprehensible. I was thinking about error-correction list decoding beyond half the minimum Hamming distance. The problem you are working on is apparently about something else. For one, I don't know what Johnson bound means in this context. $\endgroup$
    – Jyrki Lahtonen
    Commented Sep 3, 2022 at 9:45
  • $\begingroup$ By the Johnson bound I mean $1 - \sqrt\rho$. Any code is list decodable for distances $\theta$ strictly less than that bound, and for Reed-Solomon codes there explicitly is a polynomial time algorithm, the Guruswami-Sudan decoder. $\endgroup$
    – U. Haboeck
    Commented Sep 3, 2022 at 13:39
  • $\begingroup$ I see. At some point (because RS-codes are MDS-codes), the list of codewords within the target radiues necessarily becomes exponentially long, but I was never truly up to speed with that, so I cannot tell how soon that happens. $\endgroup$
    – Jyrki Lahtonen
    Commented Sep 3, 2022 at 13:52
  • $\begingroup$ Thanks anyway for your valuable comment! $\endgroup$
    – U. Haboeck
    Commented Sep 3, 2022 at 14:29

0

Reset to default

You must log in to answer this question.