Transcript sergey-ccc08

Locally Decodable Codes from
Nice Subsets of Finite Fields and
Prime Factors of Mersenne Numbers
Kiran Kedlaya
Sergey Yekhanin
MIT
Microsoft Research
An Inequality

Error Correcting Codes
n bit message
0 1
Decoder processes the (corrupted) codeword
… 0 1
Adversarial
noise
N bit codeword
0 010
…
011
0 1 1 0
…
0 0 1
In classical error correcting codes decoder needs to
process the whole (corrupted) codeword to recover
even a single bit of the original message!
Locally Decodable Codes
Codes with sub-linear decoding complexity!
n bit message
0 1
Decoder reads only k bits
… 0 1
Adversarial
noise
N bit codeword
0 010
…
011
0 1 1 0
…
0 0 1
Definition: A code C encoding n bits to N bits is called k-LDC if
given a (linearly) corrupted codeword one can recover any
particular bit of the message (w.h.p.) by reading only k randomly
chosen bits.
Locally Decodable Codes
• Example: There is a 2-query LDC of length Exp(n).
• Major question:
What is the length of optimal k-query LDCs?
• Applications:
–
–
–
–
Cryptography (private information retrieval).
Worst-case to average case reductions.
Fault tolerant computation.
Data transmission / storage.
LDCs: progress in bounds
• 2-query: Tight bound - Exp(n) [KdW].
Primes
• 3-query:
Mersenne primes
Lower bound: - Ω(n2 / log log n) [W].
Upper bounds:
- Exp(n1/2) [BIK]. (Polynomial interpolation.)
- Exp(n1/t), where 2t-1 is prime [Y]. (Point removal method.)
 Exp(n1/32,582,657) -
unconditionally.
 Exp(no(1)) - if there exist infinitely many Mersenne primes.
• Goal: Obtain constant-query LDCs of length Exp(no(1))
unconditionally.
This work
We undertake an in-depth study of the point removal
method of [Y] to answer two questions:
• Are Mersenne primes essential to the method?
• Has the method been pushed to its limit?
Heart of the point removal method
• Definition: A set S  Fq is t - combinatorially nice if ….
• Definition: A set S  Fq is k - algebraically nice if ….
• Theorem: If for some Fq there exists S  Fq such that:
- S is t-combinatorially nice and
- S is k-algebraically nice;
then there exist k-query LDCs of length Exp(n1/t).
Lemma: Let p = 2t-1 be a Mersenne prime; then S = {1,2,4,…,2t-1}
in Fp is t-combinatorially nice and 3-algebraically nice.
Are Mersenne primes essential?
Primes
Answer: No.
Mersenne numbers with large prime
factors are good enough!
Large prime factors of
Mersenne numbers
Mersenne primes
Theorem: Let  > 0. If P(2t-1) > (2t-1) = p; then
{1,2,…,2t-1}  Fp is t-comb. nice and k()-algebr. nice; thus
exist k() – query LDCs of length Exp(n1/t).
Notation: P(m) = the largest prime factor of m.
Has the method been pushed to its limit?
Answer: Yes.
Unless we progress on some old number theory questions.
Primes that are somewhat large factors of Mersenne numbers
are necessary!
Theorem: If for infinitely many t there is an Fq and S  Fq that is kalgebraically nice and t-combinatorially nice; then infinitely often:
P(2t-1) > ( t / 2 )1+1 / (k-2).
The largest function f(t) for that P(2t-1) > f(t) unconditionally
infinitely often is: f(t) = t log2 t / log log t. [Stewart]
LDCs and factors of Mersenne numbers
Known
P(2t-1) > t log2 t / log log t
P(2t-1) > (t /2)1+1/(k-2)
Necessary
P(2t-1) > (2t-1)
Sufficient
P(2t-1) = 2t-1
Goal: Obtain constant-query codes of subexponential length.
About the proof
• Mersenne numbers with large prime factors
yield nice subsets.
• Nice subsets of finite fields yield Mersenne
numbers with somewhat large prime factors.
(We will see a piece of the second proof.)
Nice subsets to large factors of Mersenne numbers
Claim: 3-algebraically nice subsets of prime fields yield
large prime factors of Mersenne numbers.
Theorem: Suppose S  Fp is 3-algebraically nice; then
- p | 2t-1;
- p > 0.75 t2.
Proof: two steps
• S  Fp is 3-algebraically nice;
then there exist 1 2 3 in Cp such that: 1 + 2 + 3 = 0.
• There exist 1 2 3 in Cp such that: 1 + 2 + 3 = 0;
then p | 2t-1 and p > 0.25 t2.
Notation: Cp - the set of p-th roots of unity in F2.
(We will go over the second step.)
Proof of the second step - I
Lemma: There exist 1 2 3 in Cp such that: 1 + 2 + 3 = 0;
then p | 2t-1 and p > 0.25 t2.
F2t
Proof:
• Let t be the smallest such that Cp  F2 t.
Cp
• p | 2t-1;
• Elements of Cp \ {1} are proper elements of F2 t i.e.,
for  in Cp \ {1}, and f(x) in F2[x], deg f < t: f() = 0.
Proof of the second step - II
Proof (continued):
• Let i denote elements of Cp.
• 1 + 2 + 3 = 0; yields 4 = 1 + 5.
– 4= 2-1.1 ; 5= 2-1.3
• Fix  in Cp such that (1+ ) is in Cp.
• Consider the set Z={a (1 + )b | a,b in [0 ,…, t/2-1]}.
• a (1 + )b c (1 + )d else we would have: f() = 0,
where deg f < t.
Thus, |Z| = (t/2)2 and hence p > (t/2)2 .
Conclusions:
• Summary:
Further progress on upper bounds for LDCs via point
removal method is tied to progress on lower bounds for
prime factors of Mersenne numbers.
• Hopes:
– Progress in number theory problems.
– Broader generalizations of the method. (finite rings?)