TOC Seminar Series: On Algorithmic Characterizations of Complexity Lower Bounds
Speaker
Rahul Santhanam
Oxford University
Host
Ryan Williams
CSAIL MIT
Abstract: An argument often made for the difficulty of proving complexity lower
bounds is that they are impossibility results, and that it is more natural and
intuitive for the human mind to argue for the feasibility of computational
tasks. But what if the challenge of proving lower bounds were to reduce to the
design or analysis of an algorithm? Surprising and counter-intuitive as this
possibility might seem, a long line of work starting in the 80s has fleshed it
out in various contexts. I will briefly survey past work on PRGs vs lower
bounds and the algorithmic method of Williams for showing non-uniform lower
bound, and then present some recent results on algorithmic characterizations of
uniform lower bounds.
Partly based on joint work with Zhenjian Lu
Milk and Cookies from 4-4:15pm, Seminar will begin at 4:15pm
bounds is that they are impossibility results, and that it is more natural and
intuitive for the human mind to argue for the feasibility of computational
tasks. But what if the challenge of proving lower bounds were to reduce to the
design or analysis of an algorithm? Surprising and counter-intuitive as this
possibility might seem, a long line of work starting in the 80s has fleshed it
out in various contexts. I will briefly survey past work on PRGs vs lower
bounds and the algorithmic method of Williams for showing non-uniform lower
bound, and then present some recent results on algorithmic characterizations of
uniform lower bounds.
Partly based on joint work with Zhenjian Lu
Milk and Cookies from 4-4:15pm, Seminar will begin at 4:15pm