Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Using Random Restrictions for Algorithmic Analysis
event speaker icon
Rahul Santhanam (Edinburgh University)
event date icon
Wednesday, 11.05.2011, 12:30
event location icon
Room 337-8 Taub Bld.
Random restrictions are commonly used for proving complexity lower bounds, eg. lower bounds on constant-depth circuits (Ajtai, Furst-Saxe-Sipser, Yao, Hastad) and lower bounds on formula size (Subbotovskaya, Impagliazzo-Nisan, Paterson-Zwick, Hastad). I will show how to use results on random restrictions to bound the running time of certain algorithms for Satisfiability which beat brute-force search. Specifically I will present an algorithm which runs in time 2^{n - \Omega(n)} on Boolean formulae of linear size and an algorithm which runs in time 2^{n - n^{1/d+1}) on unbounded fan-in circuits of poly(n) size and depth $d$.

I will also mention some more recent results motivated by our work and make some general remarks on the connections between complexity lower bound techniques and algorithmic analysis.