[Colloquium] THEORY SEMINAR TODAY: Eric Allender

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, October 19, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Eric Allender

From:		Rutgers

Web page:	http://www.cs.rutgers.edu/~allender/

Title: 		Limits on the Computational Power of Random Strings

Abstract:  

R, the set of Kolmogorov-random strings, is a central notion in the study
of algorithmic information theory, and in recent years R has increasingly
been studied in relation to computational complexity theory.  This talk takes
as its starting point three strange inclusions that have been proved since 2002:
1. NEXP is contained in the class of problems NP-Turing-reducible to R.
2. PSPACE is contained in the class of problems poly-time Turing-reducible to R.
3. BPP is contained in the class of problems poly-time truth-table-reducible to R.
(These inclusions hold for both of the most widely-studied variants of Kolmogorov
complexity: the plain complexity C(x) and the prefix-complexity K(x).  They also
hold no matter which "universal" Turing machine is used in the definitions of the
functions C and K.)

These inclusions are "strange" since R is not even computable!  Thus it is not at
all clear that these are meaningful upper bounds on the complexity of BPP,
PSPACE, and NEXP, and indeed it is not at all clear that it is very interesting to
consider efficient reductions to noncomputable sets such as R.

In this talk, I will try to convince you that the class of problems efficiently
reducible to R is, indeed, a complexity class.  The main theorems are that,
if we restrict attention to prefix complexity K and the corresponding set
of random strings R_K, then the class of decidable problems that are in
NP relative to R_K (no matter which universal machine is used to define K)
lies in EXPSPACE, and the class of decidable problems that are poly-time
truth-table reducible to R_K (no matter which universal machine is used
to define K) lies in PSPACE.

Thus we can "sandwich" PSPACE between the class of problems truth-table-
and Turing-reducible to R_K, and the class of decidable problems that are
in NP relative to R_K lies between NEXP and EXPSPACE.  The corresponding
questions for plain Kolmogorov complexity C are wide open; no upper bounds
are known at all for the class of decidable problems efficiently reducible to R_C.

These results also provide the first quantitative limits on the applicability of
uniform derandomization techniques.

This is joint work with Luke Friedman and William Gasarch.  A preliminary version
of the paper is available at http://ftp.cs.rutgers.edu/pub/allender/limitsk.pdf

Refreshments will be served prior to the talk at 2:30 in Ryerson 255.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20101019/8f939d74/attachment.htm