85. matematické kolokvium KAM - Ryan Williams (Stanford Univ.): Recent progress in non-uniform circuit complexity

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.

CV

Ryan Williams studoval na Carnegie-Mellon Univesrite v Pittsburgu, kde získal doktorát pod vedením Manuela Bluma. Posléze byl na stáži v předních institucích (např. IAS Princeton, IBM Almaden). V současnosti je asistent professorem informatiky na Stanfordské universitě. V nedávné minulosti mu bylo uděleno prestižní Sloanovo stipendium a Microsoft Faculty Fellowship. Přes své mládí získal řadu ocenění a "best paper awards" na předních konferencích v teoretické informatice. Výrazem toho je i pozvání na zvanou přednášku na ICM 2014. Jeho práce o sožitosti vzbudily velkou mezinárodní odezvu a jsou rovněž námětem jeho pražského kolokvia.