Valentine Kabanets, Russell Impagliazzo

We show that derandomizing Polynomial Identity Testing is,

essentially, equivalent to proving circuit lower bounds for

NEXP. More precisely, we prove that if one can test in polynomial

time (or, even, nondeterministic subexponential time, infinitely

often) whether a given arithmetic circuit over integers computes an

identically zero polynomial, then either ...
more >>>

Piotr Faliszewski

In this paper we define a many-one reduction which is allowed to work in exponential time but may only output polynomially many symbols. We show that there are no NEXP-hard sparse languages under our reduction unless EXP=UEXP.

more >>>Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.

The Kolmogorov measures that have been ...
more >>>

Eric Allender

It is a trivial observation that every decidable set has strings of length $n$ with Kolmogorov complexity $\log n + O(1)$ if it has any strings of length $n$ at all. Things become much more interesting when one asks whether a similar property holds when one

considers *resource-bounded* Kolmogorov complexity. ...
more >>>

Eric Allender, Luke Friedman, William Gasarch

Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K ... more >>>

Abuzer Yakaryilmaz

We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on space-bounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems ... more >>>

Dung Nguyen, Alan Selman

We investigate autoreducibility properties of complete sets for $\cNEXP$ under different polynomial reductions.

Specifically, we show under some polynomial reductions that there is are complete sets for

$\cNEXP$ that are not autoreducible. We obtain the following results:

- There is a $\reduction{p}{tt}$-complete set for $\cNEXP$ that is not $\reduction{p}{btt}$-autoreducible.

more >>>

Bin Fu

We show that

derandomizing polynomial identity testing over an arbitrary finite

field implies that NEXP does not have polynomial size boolean

circuits. In other words, for any finite field F(q) of size q,

$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where

$PIT_q$ is the polynomial identity testing problem over F(q), and

NSUBEXP is ...
more >>>

Christian Glaßer, Maximilian Witek

We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:

- For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible.

- For P, the delta-levels of ...
more >>>