Title: Algorithmic Analysis and Complexity Lower Bounds
Speaker: Rahul Santhanam (Univeristy of Edinburgh)

Date & Time:  May 21st, 2013, 15:30-16:30
Place: Tokyo Tech. CIC at Tamachi, 2F, Meeting Room #1

Abstract: I will give an overview of recent work on connections between
complexity lower bounds and algorithms for Satisfiability beating brute
force search. On the one hand, Williams established a formal connection
from non-trivial SAT algorithms to circuit lower bounds, and used this
connection to prove that NEXP not in ACC_0. On the other hand, new
algorithms for Satisfiability have been found and analyzed recently by
Impagliazzo-Mathews-Paturi, Seto-Tamaki and myself, with the analysis in
each case inspired by complexity lower bound techniques. In addition to
surveying recent work, I will give some high-level arguments why
algorithmic methods are a promising approach to circuit lower bounds,
and indicate some of the main open problems in this area.

host: Osamu Watanabe and Benjamin Rossman
watanabe@is.titech.ac.jp