### DIMACS Theoretical Computer Science Seminar

Title: A Generic Time Hierarchy for Semantic Models With One Bit of Advice

Speaker: **Dieter van Melkebeek**, The University of Wisconsin

Date: December 20, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We show that for any reasonable semantic model of computation and for
any positive integer a and rationals 1 <= c < d, there exists a language
computable in time n^d with a bits of advice but not in time n^c
with a bits of advice. A semantic model is one for which there exists a
computable enumeration that contains all machines in the model but may
also contain others. We call such a model reasonable if it has an
efficient universal machine that can be complemented within the model
in exponential time and if it is efficiently closed under deterministic
transducers.

Our result implies the first such hierarchy theorem for randomized
machines with zero-sided error, quantum machines with one- or zero-sided
error, unambiguous machines, symmetric alternation, Arthur-Merlin games
of any signature, interactive proof protocols with one or multiple provers,
etc. Our argument yields considerably simpler proofs of known hierarchy
theorems with one bit of advice for randomized or quantum machines with
two-sided error and randomized machines with one-sided error.

Our paradigm also allows us to derive stronger separation results in a
unified way. For models that have an efficient universal machine that can be
simulated deterministically in exponential time and that are efficiently
closed under randomized reductions with two-sided error, we establish the
following: For any constants a and c, there exists a language computable
in polynomial time with one bit of advice but not in time n^c with
(a log n) bits of advice. In particular, we obtain such separation for
randomized and quantum machines with two-sided error. For randomized
machines with one-sided error, we get that for any constants a and c
there exists a language computable in polynomial time with one bit of
advice but not in time n^c with (a log n)^{1/c} bits of advice.

This is joint work with Konstantin Pervyshev.