Oded Goldreich, Avi Wigderson

In the theory of pseudorandomness, potential (uniform) observers

are modeled as probabilistic polynomial-time machines.

In fact many of the central results in

that theory are proven via probabilistic polynomial-time reductions.

In this paper we show that analogous deterministic reductions

are unlikely to hold. We conclude that randomness ...
more >>>

Jan Krajicek

We study the diagonalization in the context of proof

complexity. We prove that at least one of the

following three conjectures is true:

1. There is a boolean function computable in E

that has circuit complexity $2^{\Omega(n)}$.

2. NP is not closed under the complement.

3. There is no ... more >>>

Alan Nash, Russell Impagliazzo, Jeff Remmel

Diagonalization is a powerful technique in recursion theory and in

computational complexity \cite{For00}. The limits of this technique are

not clear. On the one hand, many people argue that conflicting

relativizations mean a complexity question cannot be resolved using only

diagonalization. On the other hand, it is not clear that ...
more >>>

Harry Buhrman, Lance Fortnow, Rahul Santhanam

We show several unconditional lower bounds for exponential time classes

against polynomial time classes with advice, including:

\begin{enumerate}

\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$

\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$

\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$

\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... 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 >>>

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

We address a natural question in average-case complexity: does there exist a language $L$ such that for all easy distributions $D$ the distributional problem $(L, D)$ is easy on the average while there exists some more hard distribution $D'$ such that $(L, D')$ is hard on the average? We consider ... more >>>