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