Definitions and Theorems about Proximity Gaps #
We define the proximity gap properties of linear codes over finite fields.
[BCIKS20] refers to the paper "Proximity Gaps for Reed-Solomon Codes" by Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf.
Main Definitions #
The proximity measure of two vectors u and v from a code C at distance d is the number
of vectors at distance at most d from the linear combination of u and v with coefficients
r in F.
Equations
Instances For
A code C exhibits proximity gap at distance d and cardinality bound bound if for every
pair of vectors u and v, whenever the proximity measure for C u v d is greater than
bound, then the distance of [u | v] from the interleaved code C ^⊗ 2 is at most d.
Equations
Instances For
The error bound ε in the pair of proximity and error parameters (δ,ε) for Reed-Solomon codes
defined up to the Johnson bound. More precisely, let ρ be the rate of the Reed-Solomon code.
Then for δ ∈ (0, 1 - √ρ), we define the relevant error parameter ε for the unique decoding
bound, i.e. δ ∈ [0, (1-ρ)/2] and Johnson bound, i.e. δ ∈ [(1-ρ)/2 , 1 - √ρ]. Otherwise,
we set ε = 0.
Equations
Instances For
Theorem 1.2 (Proximity Gaps for Reed-Solomon Codes) in [BCIKS20].