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.
Using {https://eprint.iacr.org/2020/654}, version 20210703:203025.
Main Definitions and Statements #
- proximity measure, proximity gap, correlated agreement,
(δ, ε)-proximity gap, proximity parameters - statement of Theorem 1.2 (Proximity Gaps for Reed-Solomon codes) in [BCIKS20].
- statements of all the correlated agreement theorems from [BCIKS20]: Theorem 1.4 (Main Theorem — Correlated agreement over lines), Theorem 1.5 (Correlated agreement for low-degree parameterised curves) Theorem 1.6 (Correlated agreement over affine spaces).
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
Definition 1.1 in [BCIKS20].
Let P be a set P and C a collection of sets. We say that C displays a
(δ, ε)-proximity gap with respect to P and the relative Hamming distance measure
if for every S ∈ C exactly one of the following holds:
- The probability that a randomly sampled element
sfromSisδ-close toPis1. - The probability that a randomly sampled element
sfromSisδ-close toPis at mostε.
We call δ the proximity parameter and ε the error parameter.
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].
Let C be a collection of affine spaces. Then C displays a (δ, ε)-proximity gap with respect to
a Reed-Solomon code, where (δ,ε) are the proximity and error parameters defined up to the
Johnson bound.
Equations
Instances For
Pretty printer defined by notation3 command.
Equations
Instances For
Pretty printer defined by notation3 command.
Equations
Instances For
Pretty printer defined by notation3 command.
Equations
Instances For
Pretty printer defined by notation3 command.
Equations
Instances For
Pretty printer defined by notation3 command.
Equations
Instances For
Equations
Instances For
The ball radius from lemma 5.3 of the Proximity Gap paper, which follows from the Johnson bound. δ₀(rho, m) = 1 - √rho - √rho/2m.
Equations
Instances For
The first part of lemma 5.3 from the Proximity gap paper.
Given the D_X (proximity_gap_degree_bound) and δ₀ (proximity_gap_johnson),
a solution to Guruswami-Sudan system exists.
The second part of lemma 5.3 from the Proximity gap paper. For any solution Q of the Guruswami-Sudan system, and for any polynomial P ∈ RS[n, k, rho] such that δᵣ(w, P) ≤ δ₀(rho, m), we have that Y - P(X) divides Q(X, Y) in the polynomial ring F[X][Y]. Note that in F[X][Y], the term X actually refers to the outer variable, Y.
The Guruswami-Sudan condition as it is stated in the proximity gap paper.
Degree of the polynomial.
- Q_multiplicity (i : Fin n) : Polynomial.Bivariate.rootMultiplicity Q (Polynomial.C (ωs i)) (Polynomial.C (u₀ i) + Y * Polynomial.C (u₁ i)) ≥ some m
Multiplicity of the roots is at least
m. The X-degree bound.
The Y-degree bound.
The YZ-degree bound.
Instances For
The claim 5.4 from the proximity gap paper. It essentially claims that there exists a soultion to the Guruswami-Sudan constraints above.
There exists a δ-close polynomial P_z for each z
from the set S.
The δ-close polynomial Pz for each z
from the set S (coeffs_of_close_proximity).
Equations
Instances For
Proposition 5.5 from the proximity gap paper.
There exists a subset S' of the set S and
a bivariate polynomial P(X, Z) that matches
Pz on that set.
The subset S' extracted from the proprosition 5.5.
Equations
Instances For
S' is indeed a subset of S
The equation 5.12 from the proximity gap paper.
Claim 5.6 of the proximity gap paper.
Claim 5.7 of the proximity gap paper.
Claim 5.7 establishes existens of a polynomial R.
This is the extraction of this polynomial.
Equations
Instances For
Claim 5.7 establishes existens of a polynomial H.
This is the extraction of this polynomial.
Equations
Instances For
An important property of the polynomial
H extracted from claim 5.7 is that it is
irreducible.
The claim 5.8 from the proximity gap paper. States that the approximate solution is actually a solution. This version of the claim is stated in terms of coefficients.
The claim 5.8 from the proximity gap paper. States that the approximate solution is actually a solution. This version is in terms of polynomials.
Claim 5.9 from the proximity gap paper.
States that the solution γ is linear in
the variable Z.
The linear represenation of the solution γ
extracted from the claim 5.9.
Equations
Instances For
The extracted P from claim 5.9 equals γ.
The set S'_x from the proximity gap paper (just before claim 5.10).
The set of all z∈S' such that w(x,z) matches P_z(x).
Equations
Instances For
Claim 5.10 of the proximity gap paper.
Needed to prove the claim 5.9.
This claim states that γ(x)=w(x,Z) if
the cardinality |S'_x| is big enough.
Claim 5.11 from the proximity gap paper.
There exists a set of points {x₀,...,x_{k+1}}
such that the sets S_{x_j} satisfy the condition
in the claim 5.10.