[Colloquium] Reminder: Guest Speaker @ TTI-C TODAY (3/6/06)

[Katherine Cumming]

**********TTI-C Guest Speaker  TODAY***********
                                Monday, March 6 
        Presented by:  Toyota Technological Institute at Chicago
 
(1)
 
Speaker: Emanuele Viola, Harvard University
Speaker's home page: http://www.eecs.harvard.edu/~viola/
 
Date: Monday, March 6, 2006 
Location: TTI-C Conference Room
Time:  10:00 am 
         
 
Title:  Derandomization: New Results and Applications
Abstract:
Randomness has proven to be a valuable resource throughout computer science.
In particular, there are several fundamental computational problems that we
know how to solve efficiently only when we have a source of randomness at
our disposal.  But to what extent is randomness really necessary for
efficient computation?

In this talk, we survey some of our results in derandomization, which is the
field that studies the possibility and implications of simulating randomized
computation deterministically.

First, we address the derandomization of restricted computational models,
focusing on constant-depth circuits.  We develop a new application of the
derandomization of constant-depth circuits to the study of the average-case
complexity of NP.  In particular, we show how to take any function in NP
that is `mildly' hard on average and transform it into one that is
`extremely' hard on average.  We also obtain a new sub-exponential time
derandomization of constant-depth circuits with few majority gates.  This is
currently the richest randomized circuit class that researchers can simulate
in sub-exponential time.

We then discuss the derandomization of general computational models.  For
general models, the only non-trivial derandomization known is the '83 result
that probabilistic polynomial time (BPP) can be simulated in the second
level of the polynomial-time hierarchy.  Perhaps surprisingly, in more than
two decades no work has addressed the running time of this simulation.  In a
recent work, we prove that a quadratic slow-down in running time is inherent
in this simulation (for relativizing techniques).  However, as our results
show, this quadratic slow-down disappears at the third level of the
polynomial-time hierarchy, and a quasilinear-time simulation becomes
possible.

No previous knowledge of complexity theory is required for this talk. 
 
----------------------------------------------------------------------------
------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.   
For information on future TTI-C talks and events, please go to the TTI-C
Events page:  http://www.tti-c.org/events.html.  TTI-C (1427 East 60th
Street, Chicago, IL  60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060306/981aaebd/attachment.htm