85. Mathematical Colloquium
Ryan Williams
Stanford University
RECENT PROGRESS IN NON-UNIFORM CIRCUIT COMPLEXITY
Friday June 21 2013 at 11:00,room S5, 2nd floor
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.
About the speaker
Ryan Williams studoval na Carnegie-Mellon Universitě 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 assistent 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 složitosti vzbudily velkou mezinárodní odezvu a jsou rovněž námětem jeho pražského kolokvia.
