[Colloquium] van Melkebeek talk today 12:45 at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK 

Speaker: Dieter van Melkebeek
University of Wisconsin-Madison

Speaker's homepage: http://www.cs.wisc.edu/~dieter/

Time: 12:45 p.m.
Date: Friday, February 20, 2004
Place: TTI (1427 E. 60th St. - Press Building)
*LUNCH PROVIDED*

Title: Language Compression and Pseudorandom Generators

Abstract: The language compression problem asks for succinct descriptions of 
the strings in a language A such that these strings can be efficiently 
recoveredfrom their description when given a blackbox for A. We study how 
close one canget to the information theoretic lower bound of k = log |A^{=n}| 
for thedescription length of strings in A of length n. 

We show that with the help of an untrusted party, Merlin, we can achieve
the information theoretic lower bound up to an additive term of O(sqrt{k}log n)
using a deterministic scheme, and up to an additive term of O(log^3(n)) using a
randomized scheme. Without the help of Merlin, we cannot even get close to the
information theoretic lower bound - we exhibit a language A for which n-k-O(log
n) bits are needed even using randomized schemes. 

Our upper bounds utilize the hardness-based pseudorandom generator construction
of Nisan and Wigderson. 

Joint work with Harry Buhrman and Troy Lee. 

If you have questions, or would like to meet the speaker, please contact
Meridel Trimble at 773-834-9873 or mtrimble at tti-c.org
 
For information on future TTI-C talks or events, please go to the TTI-C
Events page: http://www.tti-c.org/events.shtml