Computer Science/Discrete Mathematics Seminar II

Random restrictions are a powerful tool used to study the complexity of boolean functions. Various classes of boolean circuits are known to simplify under random restrictions. A prime example of this, discovered by Subbotovskaya more than 60 years ago, is the fact that boolean formulas over the {and, or, not} basis shrink in size when the inputs are randomly restricted. Shrinkage can be used to prove worst- and average-case lower bounds, construct explicit pseudorandom generators, and design satisfiability algorithms. This talk will survey what is known about shrinkage and its applications to formula lower bounds and pseudorandomness. We will also discuss an analogue of shrinkage in the setting of algebraic formulas.