Reed Solomon Codes
Reed-Solomon codes and their algebraic structure, as used in proof systems and in coding-theoretic cryptography.
| Status | Problem | Tags |
|---|---|---|
|
RS Proximity Gaps to Capacity Proved up to the Johnson/Guruswami-Sudan bound \(\delta<1-\sqrt{\rho}\); conjectured up to capacity \(\delta\le 1-\rho-\eta\). The source records that nothing known contradicts \(c_1=c_2=2\), and that in characteristic greater than the degree nothing known contradicts \(c_1=c_2=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