ColloquiaSatyanarayana Lokam talk on July 18 (with abstract)

[Nita Yack]

COMPUTER SCIENCE
The University of Chicago
TALK



Thursday, July 18, 2002
3:30 p.m.
Ryerson 251



Satyanarayana V. Lokam, Assistant Professor,
University of Michigan
(former UChicago graduate student)

http://www.eecs.umich.edu/~satyalv/


Title: Lower Bounds for Locally Decodable Codes

Abstract:  An error-correcting code is said to be *locally  decodable* if a 
randomized algorithm can recover any single bit of a message by reading 
only a small number of symbols of a possibly corrupted encoding of 
the  message. Locally decodable codes arise in several contexts in 
computational complexity and cryptography: self-correcting computations, 
probabilistically checkable proofs, conversion of  worst-case hardness to 
average-case hardness in the construction of  pseudo-random generators, 
communication complexity, and private  information retrieval.  Katz and 
Trevisan (STOC 2000) showed that any such code $C:{0,1}^n --> \Sigma^m$, 
mapping n-bit messages to m-symbol codewords over alphabet $\Sigma$, with a 
decoding algorithm that makes at most $q$ probes must satisfy $m= 
\Omega((n/ \log |\Sigma|)^{q/(q-1)})$. They assumed that the decoding 
algorithm is non-adaptive, and left open the question of proving similar 
bounds for adaptive decoders.  We extend the Katz--Trevisan bound to 
adaptive  decoders. An important ingredient of our proof is a randomized 
method for *smoothening* an adaptive decoding algorithm. Our poof uses the 
*Second Moment Method*.

This is joint work with Amit Deshpande, Rahul Jain, T. Kavitha, and 
Jaikumar Radhakrishnan.


Host: Laci Babai
*The talk will be followed by refreshments in Ryerson 255*
Persons who need assistance should call 773-702-6614


*********************************
Nita Yack
Departmental Administrator
Computer Science
Ry 151
(773) 702-6019
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20020712/2b946b35/attachment.htm