Recent Advances Towards Proving P=BPP

Two independent techniques have been developed recently that yield sufficient conditions for P = BPP in terms of worst-case circuit complexity of functions computable in exponential time. Andreev, Clementi and Rolim proved that P = BPP provided that a sparse "efficiently enumerable" language exists of sufficiently high circuit complexity. This result has been subsequently improved by Impagliazzo and Wigderson by showing that either P = BPP or all the decision problems solvable in time 2 O(n) are solvable by circuits of size 2 o(n) . In this column we discuss these results and their relation with previously known sufficient conditions for P = BPP. 1 Introduction Randomness is very useful in the design of efficient algorithms for several important problems. Probabilistic algorithms are often the simpler ones to solve a given problem, or the most efficient, or the only efficiently parallelizable ones (see [9]). For some problems, including primality testing and approximation of # P-..