Circuit Complexity meets the Theory of Randomness

There has been remarkable progress in a field known as “derandomization” – leading to a situation where most experts now believe that any probabilistic algorithm can be replaced by a deterministic algorithm with comparable complexity. The tools and techniques of derandomization have also opened new connections between two fields that had previously seemed to have little connection to each other: 1. the field of circuit complexity (in which we try to find the most efficient circuitry to compute a given Boolean function), and 2. the field of algorithmic information theory (aka “Kolmogorov Complexity”), which provides a mathematical definition of “randomness”.

This lecture will introduce the listener to these two fields, and show how the study of derandomization has opened links that have enriched each field. In particular, the lecture will present theorems that suggest that two familiar complexity classes:

BPP: the class of problems that can be solved with negligible error in polynomial-time, and * NEXP: the class of problems solvable in nondeterministic exponential time can be characterized in terms of efficient reductions to the (undecidable) set of Kolmogorov-random strings.

Here are links to some papers related to this talk:

Speaker Biography

Eric Allender is widely recognized as a leading researcher in computational complexity theory. He has given numerous invited addresses at computer science symposia worldwide. He received a B.A. from the University of Iowa in 1979, majoring in Computer Science and Theater, and a Ph.D. from Georgia Tech in 1985. He has been at Rutgers University since then, serving as department chair from 2006 to 2009. He is a Fellow of the ACM, is Editor-In-Chief of ACM Transactions on Computation Theory, and serves on the editorial boards of Computational Complexity, and The Chicago Journal of Theoretical Computer Science. During the 2009/2010 academic year, he was a Fulbright Fellow in South Africa.