New upper bounds for Formula Satisfiability based on Random Restrictions

Rahul Santhanam, The University of Edinburgh

I will describe what appears to be a new technique for bounding running time of algorithms for SAT, based on proving concentration versions of results about random restrictions. I will apply this methodology to derive a 2^{n - \Omega(n)} upper bound for SAT on formulae of linear size. One novelty of the approach is that though the algorithm used is a simple and natural deterministic algorithm, the analysis is probabilistic. I will also describe connections between upper bounds in this context and lower bounds - as an example, I will use the technique to get a nearly optimal average-case lower bound for Parity against linear size formulae. I will pose some questions which are relevant to extending this line of research to satisfiability and lower bounds for polynomial-size constant-depth circuits.