Proximity Testing
Testing whether a vector is close to a code, and the proximity gaps and correlated-agreement statements that make such tests sound.
| 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) |
No matching items