We report progress on the \NL\ vs \UL\ problem. \begin{itemize} \item[-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$. \item[-] We investigate the complexity of min-uniqueness - a central notion in studying the \NL\ vs \UL\ problem. \begin{itemize} \item ... more >>>

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction ... more >>>

We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting consequences: 1. The measure hypothesis: NP does not have p-measure 0. 2. The pseudo-NP hypothesis: there is an NP language that can be distinguished from any DTIME(2^n^epsilon) language by an NP refuter. ... more >>>

Under the assumption that NP does not have p-measure 0, we investigate reductions to NP-complete sets and prove the following: - Adaptive reductions are more powerful than nonadaptive reductions: there is a problem that is Turing-complete for NP but not truth-table-complete. - Strong nondeterministic reductions are more powerful than deterministic ... more >>>

We apply recent results on extracting randomness from independent sources to ``extract'' Kolmogorov complexity. For any $\alpha, \epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show how to use a constant number of advice bits to efficiently compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) > (1-\epsilon)|y|$. ... more >>>

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glasser et al., complete sets for all of the following complexity classes are m-mitotic: ... more >>>

Yao (in a lecture at DIMACS Workshop on structural complexity and cryptography) showed that if a language L is 2-locally-random reducible to a Boolean functio, then L is in PSPACE/poly. Fortnow and Szegedy quantitatively improved Yao's result to show that such languages are in fact in NP/poly (Information Processing Letters, ... more >>>

We show the following results regarding complete sets: NP-complete sets and PSPACE-complete sets are many-one autoreducible. Complete sets of any level of PH, MODPH, or the Boolean hierarchy over NP are many-one autoreducible. EXP-complete sets are many-one mitotic. NEXP-complete sets are weakly many-one mitotic. PSPACE-complete sets are weakly Turing-mitotic. If ... more >>>

We consider Arthur-Merlin proof systems where (a) Arthur is a probabilistic quasi-polynomial time Turing machine and (AMQ)(b) Arthur is a probabilistic exponential time Turing machine (AME). We prove two new results related to these classes. more >>>

The Turing and many-one completeness notions for $\NP$ have been previously separated under {\em measure}, {\em genericity}, and {\em bi-immunity} hypotheses on NP. The proofs of all these results rely on the existence of a language in NP with almost everywhere hardness. In this paper we separate the same NP-completeness ... more >>>

We study several properties of sets that are complete for NP. We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$ such that for ... more >>>

We prove that if for some epsilon > 0 NP contains a set that is DTIME(2^{n^{epsilon}})-bi-immune, then NP contains a set that 2-Turing complete for NP but not 1-truth-table complete for NP. Lutz and Mayordomo (LM96) and Ambos-Spies and Bentzien (AB00) previously obtained the same consequence using strong hypotheses involving ... more >>>

We use hypotheses of structural complexity theory to separate various NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we make ... more >>>