Given a problem, can we realistically solve it using computers? Complexity theory aims to answer this question by describing how many resources we need to compute the solution as a function of the problem size. Typical resources include time on sequential and parallel architectures, and memory space. As we want to abstract away from details of input representation and specifics of the computer model, we end up with classes of problems which we can solve within certain robust resource bounds. We often focus on decision problems, or equivalently, on recognizing the corresponding language of yes instances. Some of the most well-studied complexity classes are:
One often tackles such questions by singling out the hardest problems in a complexity class, and concentrating on their properties. We consider a problem A hard for a complexity class if we can efficiently reduce every problem in the complexity class to A, i.e., if we can efficiently solve any problem in the class when given access to an oracle providing solutions to instances of A. If A itself also belongs to the class, we call A complete for the class. Several complexity classes have complete problems under various reducibility notions.
In joint work with L. Fortnow, R. Lipton, and A. Viglas, I established such lower bounds for algorithms that use little memory space. We showed that any random-access machine deciding satisfiability in subpolynomial space has to run for at least n1.618 time on formulas of length n. More generally, we obtained a time-space lower bound for satisfiability: For any constant a less than the golden ratio we determined a positive constant b such that every algorithm for satisfiability that runs in time at most na has to use space at least nb. [paper]
Together with R. Raz, I proved a pure time lower bound for satisfiability but on a more restricted model of computation: Any deterministic Turing machine with one d-dimensional work tape and random access to the input that solves satisfiability has to run for at least na steps where a is any constant less than ((d+2)/(d+1))1/2. [paper]
All of the above lower bounds hold for virtually any of the known NP-complete problems. Somewhat weaker lower bounds hold for solving coNP-complete problems like the language of propositional tautologies on nondeterministic machines.
In the paper with S. Diehl, we establish stronger time-space lower bounds for problems complete for higher levels of the polynomial-time hierarchy on randomized machines with two-sided error. [paper]
I also wrote a survey paper on lower bounds for satisfiability and related problems.
Some of the most fundamental results in computational complexity are time hierarchies - that we can solve more decision problems on some model of computation when given a bit more of some resource. Such hierarchies have been established for any reasonable model of computation that is syntactic, i.e., for which there exists a computable enumeration of all machines in the model. The latter property strongly correlates with the existence of complete problems in the corresponding polynomial-time complexity classes. The standard deterministic and nondeterministic models of computation are all syntactic; the known hierarchy theorems imply the existence of infinite time hierarchies within classes like P and NP.
However, several relevant models of computation are provably not syntactic. Examples include semantically defined models like randomized or quantum machines with bounded two-, one-, or zero-sided error. For instance, there does not exist a computable enumeration of all randomized machines that satisfy the promise of bounded two-sided error (that no input is accepted with probability close to 1/2). This relates to the fact that there is no known complete problem for BPP, the class of all languages which have polynomial-time randomized decision procedures with bounded two-sided error.
To date, no nontrivial hierarchy theorem is known for any non-syntactic model. In joint work with K. Pervyshev, I established a time hierarchy for any reasonable model of computation with one bit of advice: For any rationals c and d such that 1 ≤ c < d, there exists a language that can be decided in time nd with one bit of advice but not in time nc with one bit of advice. In particular, we obtained infinite time hierarchies within the polynomial-time complexity classes corresponding to each of the models listed above with one bit of advice. [paper]
J. Kinne and I investigated the corresponding problem for space rather than time. [paper]
A language is sparse if it contains no more than polynomially many of the exponentially many instances of each length. Showing that P has no sparse hard language under logarithmic space computable reductions would separate L from P.
I established the logical completeness of this approach for reductions that can ask a bounded number of queries: If L differs from P then there exists no sparse hard language for P under logarithmic space reductions with a bounded number of oracle queries. The proof works for various other classes as well, e.g., for L versus NL, and for NC1 versus L. Another instantiation states that no sparse hard language for NP exists under polynomial-time randomized reductions with a bounded number of queries unless randomness allows us to solve any NP problem in polynomial time. [paper]
Together with M. Ogihara, I also wrote a survey paper on sparse hard languages for P.
The existence of optimal proof systems for tautologies turns out to be related to the existence of complete languages for the class of sparse NP languages. In joint work with H. Buhrman, L. Fortnow, and S. Fenner we investigate the existence of such complete languages. [paper]
A language is polynomial-time reducible to a sparse language iff it has polynomial-size circuits. In joint work with L. Antunes and L. Fortnow, we found an alternative characterization based on the intuitively appealing notion of computational depth. [paper]
Joint work with H. Buhrman, L. Fortnow, and L. Torenvliet established that large complexity classes like doubly exponential space have complete languages that are not autoreducible, whereas the complete languages of smaller classes like exponential time all share the property of autoreducibility. The specific results we got yielded alternate proofs of known separations. We also showed that settling the question for doubly exponential time either way, would imply major new separations: It would either separate P from PSPACE, and NL from NP, or else the polynomial-time hierarchy from EXP. [paper]
We used these results on autoreducibility in our work on resource bounded measure and the BPP versus EXP problem.
Within the formalism of resource bounded measure, most languages turn out to be hard for BPP under relatively powerful reductions. On the other hand, H. Buhrman and I proved that EXP and several other subclasses only have a few complete or hard languages under weaker reducibilities. A very narrow gap between the power of the reductions remains, and bridging it would separate BPP from EXP and from certain other classes. We also showed that EXP only has a few complete languages under polynomial time reductions that make all their queries in a nonadaptive way unless the polynomial-time hierarchy collapses. [paper]
Another approach for settling the BPP versus EXP problem, similar in spirit to the probabilistic method of combinatorics, tries to show that BPP is a small subclass of EXP. I proved the logical completeness of this strategy, i.e., if BPP differs from EXP then it is a small subclass of EXP. As a by-product, I obtained the first nontrivial example of a class for which the equivalent of the 0-1 Law in resource bounded measure holds. [paper]
One can view resource bounded measure as a restriction of classical Lebesgue measure that preserves several nice properties like additivity and monotonicity. Whether invariance under permutations also carries over, remains open. H. Buhrman, K. Regan, D. Sivakumar, M. Strauss, and myself investigated the resource bounded equivalent of permutation invariance, and showed that it holds if strong pseudo-random generators exist. Autoreducibility plays a crucial role in this context. We argued that if resource bounded permutation invariance holds, then autoreducibility is rare within EXP. Using our results about the connection between autoreducibility and completeness, we showed that the latter implies that BPP differs from EXP - yet another way of tackling the BPP versus EXP problem. We also proved that few languages in EXP are nonadaptively autoreducible unless the polynomial-time hierarchy collapses. [paper]
Randomness has become a standard tool in various areas of computer science: sequential, parallel, and distributed computing, cryptography, interactive proof checking, ... It often allows us to come up with efficient and simple solutions. However, from a complexity theoretic point of view, the power of randomization remains unclear. One fundamental question is whether we can simulate randomized computations deterministically without a significant blowup in running time.
A celebrated recent result in this context is the deterministic polynomial-time primality test by M. Agrawal et al., which was obtained by derandomizing a randomized polynomial-time primality test. The above question asks whether the same can be done for arbitrary randomized computations. The consensus within the complexity community suggests a positive answer, although an inherent exponential slowdown is not yet ruled out (the BPP versus EXP problem). The known results are all conditional: Under certain complexity theoretic hypotheses regarding the existence of hard problems, we can construct pseudorandom generators that allow us to simulate efficient randomized computations by efficient deterministic computations. The hypotheses have been simplified over the years but they are yet to be removed.
I have looked at the role of randomness in bounded round interactive proof systems known as Arthur-Merlin games. Under certain hardness conditions, Arthur (the verifier) can use a pseudo-random generator to reduce the number of random bits he needs. The strongest hardness condition yields complete derandomizations. The weakest one provides the first evidence that any language with a bounded round interactive proof system, and graph nonisomorphism in particular, has subexponential size proofs: If not, the polynomial-time hierarchy collapses. [paper]
Together with A. Klivans, I applied the same derandomization technique to various other randomized processes: [paper]
I have also looked at the BPP versus EXP problem from various angles. In this context, R. Santhanam and I proved the first unconditional, albeit small, improvement over the trivial deterministic simulation of randomized time t: We showed how to simulate randomized multitape Turing machines operating in time t on deterministic Turing machines operating in time o(2t). [paper]
It turns out that the conditional derandomization results mentioned above have unconditional implications in other areas of complexity theory that - at first sight - do not involve derandomization at all.
One such application relates to the search for computational problems of intermediate complexity. We know that if P differs from NP, then there are problems in NP that are not in P but are not NP-complete either. In fact, there exists a whole hierarchy of such problems under the hypothesis that P differs from NP. However, almost all of the known natural problems in NP have been categorized as either in P or else NP-complete. There are only a handful of candidate NP-intermediate natural problems (including factoring and graph isomorphism). A similar situation holds for complexity classes like PSPACE, and for the relationship between completeness notions for the same complexity class based on different types of reductions. In these contexts, sets of strings of high Kolmogorov complexity (for various Kolmogorov measures) have been proposed as natural candidates for languages that are not complete for the class they naturally live in. The Kolmogorov complexity of a string is the length of its shortest description; various complexity restrictions on the descriptions lead to various notions of Kolmogorov complexity.
The intuition was that sets of strings of high Kolmogorov complexity did not have enough structure to allow us to encode every possible problem of the underlying complexity class. In fact, one can typically prove that these sets are not complete under fairly restrictive types of reductions, such as logspace Karp reductions in the case of PSPACE. The prevailing belief was that the same held for more powerful reductions. Contrary to that belief, in joint work with E. Allender, H. Buhrman, M. Koucky, and D. Ronneburger, I showed that these sets are complete under somewhat more powerful reductions, such as polynomial-time zero-error randomized Cook reductions in the case of PSPACE. Thus, we obtained the first natural examples of sets that separate the weaker and stronger completeness notions for PSPACE. The proofs exploit an interpretation of the conditional derandomization results as connecting two common notions of "random strings": a string picked (uniformly) at random, and a string without a short description. [paper]
Another application deals with data compression, more specifically with the so-called language compression problem. The latter asks for succinct descriptions of the strings in a language A such that the strings can be efficiently recovered from their description when given access to A. Let A=n denote the set of strings in A of length n. Information theoretically, we need k = log |A=n| bits to be able to describe every possible string in A=n, and we can essentially realize that lower bound: Describe a string in A=n by its length n and its lexicographic index in A=n. However, it may take exponential time to recover a string from that description. H. Buhrman, T. Lee, and I studied how close one can get to the information theoretic lower bound with efficient reconstruction schemes. Without any additional help, it turns out one cannot get close at all: We exhibited a language A for which n - k - O(log n) bits are needed, even for randomized schemes. With the help of an untrusted party, though, we showed how to achieve the information theoretic lower bound up to an additive term of O((k1/2 + log n) log n) using a deterministic scheme, and up to an additive term of O(log3 n) using a randomized scheme. [paper]
In the space-bounded setting, nontrivial derandomization results have been known for some time. In particular, N. Nisan showed how to simulate randomized logspace by a deterministic algorithm that runs in polynomial time and space Θ(log2 n), and M. Saks and S. Zhou established a deterministic algorithm that runs in time nΘ(log0.5n) and space Θ(log1.5 n). In joint work with J.-Y. Cai and V. Chakaravarthy, I obtained a family of deterministic simulations whose time and space complexities interpolate between these earlier results: For any 0 ≤ a ≤ 0.5, randomized logspace can be simulated deterministically in time nO(log0.5-an) and space O(log1.5+an). [paper]
I have done a little bit of work in this area. Grover's algorithm can be interpreted as a procedure for computing the OR function in a quantum black-box model. Together with Tom Hayes and Sandy Kutin, I developed some quantum black-box algorithms for computing the majority function. They provably outperform any classical algorithm. [paper]
Currently, I am particularly interested in the relationship between BQP, the class of all languages which have polynomial-time quantum algorithms with bounded two-sided error, and the polynomial-time hierarchy, and in hierarchies within BQP.
The intriguing results on IPS's and PCP's of the early nineties got me interested in computational complexity theory. They also brought me to the University of Chicago, where a lot of the initial work on them was done, e.g., the conception of Arthur-Merlin games, equivalent to bounded round interactive proof systems. By the time I arrived at the University of Chicago, research interests there had shifted to other areas of computational complexity theory, and mine moved along. Nevertheless, I remain very interested in IPS's and PCP's.
One aspect I investigated was the role of randomness in Arthur-Merlin games. I obtained some conditional derandomization results, e.g., that that every language with a bounded round interactive proof system has subexponential size proofs unless the polynomial-time hierarchy collapses. This provided the first strong evidence that graph nonisomorphism has subexponential size proofs of membership. [paper]