The Taub Faculty of Computer Science Events and Talks

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.