**Date & Time:** Friday, July 31, 2015, 14:00-15:00.

**Venue:** Ramanujan Hall

**Title:** Meta algorithms and circuit lower bounds

**Speaker:** Srikanth Srinivasan, IIT Bombay

**Abstract:** Of late, there has been quite some work relating to the
connections between complexity theoretic circuit lower bounds on the
one hand and algorithms for problems related to circuits on the other.
I will review some results in this direction, starting with a result
of Paturi, Pudlak and Zane on the number of isolated satisfying
assignments of a Boolean formula in k-CNF form. The result itself can
be found here:

http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/paturi97satisfiability.pdf