[Colloquium] Guest Speaker announcement

[Ponda Barnes]

Guest Speaker 
 
Presented by: Toyota Technological Institute at Chicago
 
Speaker: Sergey Yekhanin
Speaker's home page: http://theory.lcs.mit.edu/~yekhanin/
 
Date: Wednesday, March 28, 2007
Time: 10:00am
Location: TTI-C Conference room
 
 
 
Title: New Locally Decodable Codes and Private Information Retrieval Schemes
 
 Abstract:
 
 A q-query Locally Decodable Code (LDC) is an error-correcting code that
encodes an n-bit message x as a codeword 
 C(x), such that one can probabilistically recover any bit x_i of the
message by querying only q bits of the codeword C(x), even after some 
 constant fraction of codeword bits has been corrupted.  The goal of LDC
related research is to minimize the length of such codes.
 
 A q-server private information retrieval (PIR) scheme is a an n-bit string
x replicated between q servers while each server 
 individually learns no information about i. The goal of PIR related
research is to minimize the communication complexity of such schemes.
 
 We present a novel algebraic approach to LDCs and PIRs and obtain vast
improvements upon the earlier work.  Specifically, given any Mersenne 
 prime p = 2^t ?  1, we design three query LDCs of length Exp (n^{1/t}),
for every n. Based on the largest known Mersenne prime, this translates to a
length 
 of less than Exp(n^{10^{?7}}), compared to Exp(n^{1/2}) in the  previous
constructions.  We also design 3-server PIR schemes with 
 communication complexity of O(n^{10^{?7}})  to access an n-bit   database,
compared to the previous best scheme with complexity  O(n^{1/5.25}).
 
 It has often been conjectured that there are infinitely many Mersenne
primes.  Under this conjecture, our constructions yield three query locally
decodable codes of sub exponential length and three server private
information retrieval schemes with sub polynomial communication complexity.
 
 
If you have any questions or would like to meet the speaker, please contact
Ponda Barnes at pondabarnes at tti-c.org
For future TTI-C talks and events, please go to
http://ttic.uchicago.edu/cal/month.php
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070320/9dd01e09/attachment.htm