Talks
Fall 2015

Satisfiability Algorithms Based on Concentrated Shrinkage

Thursday, October 1st, 2015, 3:15 pm3:30 pm

Add to Calendar

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.