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.
O přednášejícím
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.