We associate to each Boolean language complexity class $\mathcal{C}$ the algebraic class $a\cdot\mathcal{C}$ consisting of families of polynomials $\{f_n\}$ for which the evaluation problem over the integers is in $\mathcal{C}$. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in $NSUBEXP$ then $a\cdot ... more >>>

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ... more >>>

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:
every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear
number of clauses. This lemma has subsequently played a key role in the study
of the exact complexity of the satisfiability problem. A natural question is
more >>>

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 >>>

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there
is a polynomial-time computable function $f$ and a set $A$ such that
for each instance ... more >>>

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For ... more >>>

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes.

We explore whether various complexity classes can have linear or
more generally $n^k$-sized circuit families for some fixed $k$. We
show

1) The following are equivalent,
- NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k
- P^NP|| is in SIZE(n^k) for some k
- ONP/1 is in ... more >>>

We consider the problem of amplifying uniform average-case hardness
of languages in $\NP$, where hardness is with respect to $\BPP$
algorithms. We introduce the notion of \emph{monotone}
error-correcting codes, and show that hardness amplification for
$\NP$ is essentially equivalent to constructing efficiently
\emph{locally} encodable and \emph{locally} list-decodable monotone
codes. The ... more >>>

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

We show that for any constant a, ZPP/b(n) strictly contains
ZPTIME(n^a)/b(n) for some b(n) = O(log n log log n). Our techniques
are very general and give the same hierarchy for all the common
promise time classes including RTIME, NTIME \cap coNTIME, UTIME,
MATIME, AMTIME and BQTIME.

We show a ... more >>>

We consider uniform assumptions for derandomization. We provide
intuitive evidence that BPP can be simulated non-trivially in
deterministic time by showing that (1) P \not \subseteq i.o.i.PLOYLOGSPACE
implies BPP \subseteq SUBEXP (2) P \not \subseteq SUBPSPACE implies BPP
= P. These results extend and complement earlier work of ... more >>>

We give the first extension of the result due to Paul, Pippenger,
Szemeredi and Trotter that deterministic linear time is distinct from
nondeterministic linear time. We show that DTIME(n \sqrt(log^{*}(n)))
\neq NTIME(n \sqrt(log^{*}(n))). We show that atleast one of the
following statements holds: (1) P \neq L ... more >>>