85 KAM Mathematical Colloquium
Ryan Williams
Stanford University
RECENT PROGRESS IN NON-UNIFORM CIRCUIT COMPLEXITY
Friday June 21 2013 at 11:00, lecture room S5, second floor
KAM MFF UK
Malostranské nám. 25
118 00 Praha 1
Abstract
A non-uniform computational model permits us to design, for every natural number n, a program P_n to be run solely on the 2^n bit strings of length n, where the size of the program P_n can itself grow with n. Such infinite computational models can be very powerful, even when the sizes and running times of P_n are bounded by a polynomial in n. Therefore a lower bound against non-uniform computation is among the strongest form of impossibility result that one can obtain in complexity theory. Correspondingly, such results are also among the most difficult to prove; the area of non-uniform computation contains many embarrassingly open questions. For example, it is still open to find a function computable in exponential time that cannot be computed with non-uniform families of programs of polynomial size and polynomial running time. (If no such function existed, then every exponential-time function could be simulated "efficiently" --- provided that one is allowed unbounded time to design a separate but short program for each input length.)In this talk, I will outline some general approaches we have recently developed to attack some of these open questions. The design of faster algorithms for circuit analysis plays a major role in the proofs. For example, the existence of nontrivial satisfiability algorithms for various circuit classes (algorithms running faster than exhaustive search) implies new non-uniform circuit lower bounds for those circuit classes.
