[Colloquium] Tomorrow: Santhanam/Dissertation Defense/5-11-05

[Margaret Jaffey]

This is a reminder about Rahul Santhanam's Dissertation Defense 
tomorrow afternoon.

--------------------------------------------------------
	Department of Computer Science/The University of Chicago

			***  Dissertation Defense ***


Candidate:  Rahul Santhanam

Date:  Wednesday, May 11, 2005

Time and Location:  2:30 p.m. in Ryerson 251

Title:  Hierarchy Theorems and Resource Tradeoffs for Semantic Classes

Abstract:
Computational complexity theory studies the minimum resources
(time, space, randomness etc.) to solve computational problems. Two
fundamental questions in this area are:
1. Can more problems be solved given more of a given resource? A 
positive
answer to this question is known as a hierarchy theorem.
2. Can one resource be traded off with another when solving a given
problem?
Such a result is known as a resource tradeoff.

We study these questions in the context of semantic classes, which are
classes for which no efficient enumeration of machines is known. Several
natural classes such as $\BPP$ (probabilistic polynomial time with two
sided error), $\RP$, $\MA$ and $\NP \cap \coNP$ are semantic classes. No
hierarchy theorems are known in general for uniform polynomial
time-bounded semantic classes. We investigate the existence of 
hierarchies
for natural variants of semantic classes, focusing mainly on semantic
classes with small advice. Complexity classes with advice are defined by
Turing machines receiving some auxiliary information depending only on 
the
input length. We prove the following results:
1. A hierarchy theorem for polynomial-time semantic classes with
    $O(\log(n) \log(\log(n)))$ bits of advice.
2. A hierarchy theorem for quasipolynomial-time semantic classes with 1
    bit of advice.
3. Hierarchy theorems for BPP and RP with 1 bit of advice.
4. Hierarchy theorems for average-case BPP and smoothed BPP.

Turning to the question of resource tradeoffs, we investigate conditions
under which randomness can be traded off for time. We show that under 
the
weak assumption that not all languages in $P$ have a simulation in
Merlin-Arthur polylogarithmic time that fools deterministic 
polynomial-time
adversaries restricted to a good error-correcting code, $BPP$ is 
contained
in deterministic subexponential time. We also study uniform assumptions
under which AM and MA can be derandomized. Finally, we show a weak 
unconditional
derandomization: every language L accepted by a probabilistic multi-tape
Turing machine in time t is accepted by a deterministic Turing machine 
in
time $2^{\delta t}$, for some $\delta < 1$.

Candidate's Advisors:  Profs. Janos Simon and Lance Fortnow


A draft copy of Mr. Santhanam's dissertation will be available soon in 
Ry 161A.

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margaret P. Jaffey				margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-