Abstract
The random restriction approach was originally used to prove formula size lower bounds, where it was shown that formulas shrink on average under random restrictions. In several recent works, this result was improved to a concentrated version where formulas shrink with high probability. This concentrated shrinkage property leads to nontrivial algorithms for Formula-SAT, MAX-SAT, etc. In this talk, we will survey techniques in showing concentrated shrinkage, and its applications in designing efficient algorithms.