Reed Solomon Codes
Reed-Solomon codes and their algebraic structure, as used in proof systems and in coding-theoretic cryptography.
| Status | Statement | Tags |
|---|---|---|
|
RS Proximity Gaps to Capacity Proved up to the Johnson/Guruswami-Sudan bound delta < 1 - sqrt(rho); conjectured up to capacity delta <= 1 - rho - eta. The source records that nothing known contradicts c1 = c2 = 2, and that in characteristic greater than the degree nothing known contradicts c1 = c2 = 1 – while those smaller exponents are provably ruled out in characteristic two. 5 open |
Proximity TestingReed Solomon CodesSnarkstight-boundbarrier (ai) | |
|
RM Gap to Capacity for BEC Conjecture 14 of the source. That Reed-Muller codes achieve capacity for the BEC is a theorem of Kudekar et al.; the gap to capacity – a polynomial rate of convergence – is open. The source needs it to strengthen its refutation of the expansion-implies-hardness conjecture for noisy k-XOR from quasi-polynomially many constraints to polynomially many, and notes the question was raised explicitly in three prior works. 4 open |
Average Case HardnessCode Based CryptographyExpander GraphsReed Solomon Codestight-bound |
No matching items