On this page...
On this page I describe my main research interests of computational complexity theory. In particular, I give background and summarize my research that has resulted in publications. Of course, I am also working on other research projects currently, but I do not describe those here. I continue to research mainly within computational complexity theory and theoretical computer science. But I am also interested in the possibility of collaborating on other projects.
Outline
- Background: Complexity Theory
- Background: Randomized Algorithms
- My Publications: Typically-Correct Derandomization
- My Publications: Hierarchy Theorems
Complexity Theory
My research interests are within theoretical computer science, specifically complexity theory. Complexity theory aims to determine how efficiently problems can be solved with respect to various resources, for example time and memory space. A complexity class is defined as the collection of problems that can be solved within given resource bounds. For example, P is the set of problems that can be decided in polynomial time, and PSPACE is the set of problems that can be decided with a polynomial amount of memory space. By considering different resources, literally hundreds of complexity classes have been defined.
- L: logarithmic space.
- P: polynomial time.
- BPP: polynomial time randomized algorithms.
- NP: polynomial time non-deterministic algorithms.
- PSPACE: polynomial memory space.
- EXP: exponential time.
The Complexity Zoo lists these and many other complexity classes. A fundamental question is how these classes relate to each other. The most famous of these is the "P versus NP" question. The question has great practical importance due to the highly successful theory of NP-completeness showing that if P = NP then a host of important optimization problems (e.g. traveling salesperson, graph coloring, maximum satisfiability) can be solved in P. An equivalent formulation of the P versus NP question is whether proofs of theorems can be found as efficiently as they can be verified. Thus the problem is also of immense philosophical importance, and is one of the seven Clay Mathematics Millenium Prize Problems.
Whether all NP problems can be solved efficiently remains open, but
there are many other important questions in complexity theory.
There have been notable and celebrated successes proving both
complexity class inclusions and separations, but still many of the
questions remain open. For a history,
see
A Short History of Computational Complexity by Lance Fortnow and Steve Homer.
Randomized Algorithms
My research has mainly focused on the power of randomized algorithms. Randomness has been a valuable algorithm design tool. Many important problems can be solved by randomized algorithms that are either much more efficient or much simpler to implement than the best-known deterministic algorithms. The important question is, are randomized algorithms truly more powerful than deterministic algorithms, or can every randomized algorithm be derandomized - converted into a deterministic algorithm without much loss in efficiency?
Early canonical examples of problems solvable much more efficiently with randomness than without include primality testing and connectivity on undirected graphs: relatively simple randomized algorithms solve primality testing in polynomial time and undirected connectivity in logarithmic memory space. In two famous separate works, both of these problems have been derandomized - Agrawal et al. giving a deterministic polynomial-time algorithm for primality and Reingold giving a deterministic logarithmic-space algorithm for undirected connectivity.
General-Purpose Derandomization These two derandomization results employ techniques that are very specific to the problems being solved. A natural question is whether there are more generic methods that can be applied to any randomized algorithm. Let A(x,r) be a randomized polynomial-time algorithm that takes input x, uses random bits r, and outputs a Boolean value. The trivial deterministic simulation of A takes the majority vote over all random strings and takes exponential time. A more efficient simulation follows if we can shrink the number of random bits needed by constructing a pseudorandom generator G, a function that takes a short random seed and outputs a longer pseudorandom string such that any polynomial-time algorithm has roughly the same probability of acceptance on a uniform output of the pseudorandom generator as on a truly uniform random string. If the pseudorandom generator has logarithmic seed length then there are polynomially many pseudorandom strings to consider, and the algorithm Majorityy(A(x,G(y)) that takes the majority vote over the pseudorandom strings is a polynomial-time deterministic simulation.
A long line of research has shown that a very reasonable
complexity-theoretic hardness assumption can be used to construct
pseudorandom generators sufficient to derandomize all time-efficient
randomized algorithms, i.e., to conclude that BPP = P.
The hardness assumption states that there is
a problem that can be solved in time 2Θ(n) but cannot
be solved by a circuit that has only 2o(n) gates.
In practice, this approach to derandomization may be too inefficient
because the randomized
algorithm needs to be executed once for each of a polynomial number of pseudorandom strings.
Further, the hardness assumption, though plausible and widely believed in the community, has
been notoriously difficult to prove and recent work has shown that in fact
any non-trivial derandomization
of certain randomized algorithms implies the existence of a hard problem.
Typically-Correct Derandomization
A recent line of work has made progress on achieving general-purpose derandomizations by relaxing the requirement that a deterministic simulation is correct on all inputs.
- For standard derandomization, also known as "everywhere-correct" derandomization, we want a deterministic algorithm that is correct on every input.
- For typically-correct derandomization, the deterministic algorithm only needs to be correct on at least 1-δ fraction of the inputs, for a small δ.
In fact, work in this area has already shown that a number of classes of randomized algorithms admit efficient typically-correct derandomizations. In the paper "Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds", I along with Dieter van Melkebeek and Ronen Shaltiel demonstrate typically-correct derandomizations for many types of randomized algorithms, including streaming algorithms, augmented constant-depth circuits, multi-party communication protocols, and decision trees. Some of these results are new to our paper, and for others we give improved parameters over previous work and/or simpler proofs.
Seed-Extending PRG Approach We prove each of the above results using a very natural generic approach. Let A(x,r) be a randomized algorithm taking input x and randomness r. We show that if a pseudorandom generator G remains secure even when its seed is revealed, a so-called seed-extending pseudorandom generator, then the deterministic simulation B(x) = A(x, G(x)) makes a small number of mistakes. Consider how this use of pseudorandom generators differs from the use outlined earlier for everywhere-correct derandomization. Whereas the use discussed earlier executes the randomized algorithm a polynomial number of times, our approach deterministically selects a single random string and executes the randomized algorithm only once. Further, the seed length of G now only needs to be a small polynomial rather than logarithmic. This relaxation allows us to obtain the unconditional derandomization results in those settings already mentioned and conditional results in others that are based on weaker hardness assumptions than previous work.
Typically-Correct Derandomization of BPP? The hope is that such typically-correct derandomization can be achieved for all efficient randomized algorithms (i.e., all of BPP), without the need for a hard problem which, as discussed above, is known to imply everywhere-correct derandomization. We demonstrate a very small δ for which typically-correct derandomization of BPP still implies the existence of a hard problem. We expect that derandomization for slightly larger values of δ is possible without the need for a hard problem, and we continue to work in this direction. As a first step, we show that typically-correct derandomization of BPP follows from a weaker hardness assumption than the one stated previously that implies everywhere-correct derandomization of BPP, i.e., BPP = P.
Another way to make progress in our understanding of randomized algorithms is to study their fundamental properties. Among the most basic questions is whether an algorithm with more resources can accomplish more than an algorithm with fewer resources.
- Time and space hierarchy theorems state that an algorithm with more time or memory space can solve strictly more problems than algorithms with fewer resources.
Diagonalization Such hierarchies were among the first properties proved of deterministic algorithms. These follow by using diagonalization: an algorithm D diagonalizes against every algorithm that uses slightly fewer resources by choosing a different input for each, simulating the algorithm on that input, and then outputting the opposite. D enumerates the smaller-resource algorithms by iterating over all possible programs. These types of techniques can be applied in a wide variety of contexts and are some of the key methods available for proving separations between complexity classes. For example, the time and space hierarchies for deterministic machines show that P ≠ EXP and that L ≠ PSPACE.
Diagonalization on Randomized Algorithms ? Consider trying to apply diagonalization to randomized algorithms. For a randomized algorithm to be useful, it should output the correct value with high probability. Equivalently, a randomized algorithm should have bounded error on every input. Thus, a time or memory-space hierarchy for randomized algorithms is given by a randomized algorithm D that (i) has bounded error on every input, and (ii) computes a language different than any computed by a bounded-error randomized algorithm that uses slightly less memory space. A naive application of diagonalization to randomized algorithms fails, as follows. In any computable enumeration of randomized machines there are algorithms that do not have bounded error; by simulating these algorithms and outputting the opposite, D likewise fails to have bounded error.
Due to these difficulties, the fundamental question of whether time and space hierarchy theorems hold for randomized algorithms remains open. For example, although unlikely and counter-intuitive it may be that all problems solvable by a randomized algorithm in time nlog n can also be solved by a linear-time randomized algorithm.
Hierarchies for Non-Uniform Randomized Algorithms Recent work by a number of researchers has come the closest yet to solving the longstanding problem by showing time hierarchy theorems for slightly non-uniform randomized algorithms. Rather than consisting of a single algorithm, a non-uniform algorithm consists of a small set of algorithms where the choice of which to execute is made “non-uniformly” depending on the size of the input. Equivalently, a certain number of "advice bits" are given for each input length to indicate which algorithm to execute. The best results use the smallest non-trivial amount of non-uniformity, by having only two algorithms to choose between for each input length (equivalently, a single advice bit to indicate which algorithm to execute). In the paper "Space Hierarchy Theorems for Randomized and Other Semantic Models", Dieter van Melkebeek and I demonstrate such hierarchy theorems for memory space rather than time.
That is, we construct a slightly non-uniform algorithm D that consists of two algorithms D1 and D2 and appropriate choices of which to execute at each input length such that D (i) has bounded error on every input, and (ii) computes a language different than any computed by a bounded-error slightly non-uniform randomized algorithm that uses slightly less memory space. In fact, even if the smaller resource machines are allowed a much larger amount of non-uniformity (choosing from a polynomial number of algorithms rather than just two or equivalently using a logarithmic number of advice bits), D still computes differently. We also derive hierarchy theorems for other types of algorithms, including for example quantum algorithms and Arthur-Merlin interactive protocols.