I'm wondering if there are good references that describe the random restriction method as a lower bound technique ? I'm aware that it's linked to the switching lemma and shows up in many different proofs, but I'm looking for a more or less self-contained explanation of the idea.
$\begingroup$
$\endgroup$
asked Jun 4 '14 at 14:26
Add a comment
|
$\begingroup$
$\endgroup$
A relatively simple setting to illustrate the method of random restrictions is Subbotovskaya's original application of the method to prove an $\Omega(n^{1.5})$ lower bound on the formula size of the parity function, where formulas use arity-2 AND and OR operations. Section 6.3. of Jukna's Boolean Function Complexity has a nice exposition. Also, see these lecture notes from Swastik Kopparty's class in Rutgers.
answered Jun 4 '14 at 18:35