University of Wyoming, USA, and CWI, Netherlands
4pm Tuesday, 10th November, 2009
Room 4.31/33, Informatics Forum
We describe two techniques for applying computational learning algorithms in computational complexity to obtain lower bounds.
1. The Winnow algorithm and other online mistake-bound learning algorithms are used to build martingale prediction strategies. This yields the solution of several open problems (Lutz and Mayordomo, 1994; Fu, 1994) about the density of hard sets for exponential time.
2. We connect exact learning via membership and equivalence queries to an extension of martingales called betting games. This allows us to relate the question of whether there is an exact learning algorithm for Boolean circuits to the question of whether exponential time has polynomial-size circuits, improving a result of Fortnow and Klivans (2009).
This is joint work with Ryan Harkins.