New Algorithms for Learning in Presence of Errors

Sanjeev Arora · Rong Ge

ICALP 2011

Time bound

2^{Õ(n^2ε)}, for αq=n^ε and fixed ε<1/2

Space bound

Exponential-size linearization; no numerical space coefficient extracted.

Source / version date

13 Dec 2010

Comparison variant

Gaussian error · algebraic bounds

Cost scale

Parameter-dependent time and space expressions

Parameters

Prime q=q(n) with q ≫ (αq log n)²; αq=n^ε, fixed 0≤ε<1/2.

Error distribution

Source Gaussian Ψ_α over GF(q), width parameter αq.

Secret distribution

Arbitrary fixed u∈GF(q)^n.

Sample budget

Oracle access; 2^{Õ(n^{2ε})} samples allowed, not a linear-sample claim.

Objective

Recover the full secret.

Cost model

Classical randomized polynomial-system linearization; polynomial input-size factors implicit.

Assumptions

Theorem for the specified Gaussian distribution and modulus regime.

Success guarantee

High probability as in Theorems 3.1 and 3.3.

Assumptions and source notes

Subexponential only in the stated small-error regime. Date is the checked ECCC revision, preceding ICALP 2011.

Source location

§3, Theorem 3.1, p. 8; construction and Theorem 3.3
Version: ECCC TR10-066 revision 1, 13 December 2010

Primary source ↗

@misc{arora-ge2010-eccc,
  author = {Sanjeev Arora and Rong Ge},
  title = {{New Algorithms for Learning in Presence of Errors}},
  year = {2011},
  url = {https://eccc.weizmann.ac.il/report/2010/066/},
  keywords = {LWE, algorithmic complexity, historical literature},
  cr_date = {2010-12-13},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {ICALP 2011, Part I, LNCS 6755, pp. 403–415; DOI 10.1007/978-3-642-22006-7_34},
  cr_author_ids = {sanjeev-arora; rong-ge},
  note = {ICALP 2011, Part I, LNCS 6755, pp. 403–415; DOI 10.1007/978-3-642-22006-7_34}
}