Rahul Santhanam: Algorithmic analysis and complexity lower bounds

I will discuss some connections between analysis of algorithms for satisfiability and complexity lower bound techniques. First I will present an algorithm for Formula-SAT which runs in time 2^{n-\Omega(n)} on formulae of linear size. The analysis of the algorithm relies on the method of random restrictions, originally used to prove formula size lower bounds.
Then I will sketch a connection between the Neciporuk lower bound technique in concrete complexity and the algorithmic technique of memoization. If time permits, I will show that the published analyses of some well-known algorithms for satisfiability are tight, and pose some questions about further connections in this vein.

The speaker was invited by Jakob Nordström.