<p>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 <a href="http://www.math.rutgers.edu/~sk1233/courses/topics-S13/lec2.pdf">lecture notes</a> from Swastik Kopparty's class in Rutgers.</p>

CC BY-SA 3.0
2014-06-04T18:35:18.727Z
2014-06-04T20:04:47.527Z
2014-06-04T20:04:47.527Z
Sasho Nikolov
<p>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. </p>

<cc.complexity-theory><reference-request><circuit-complexity>
A good exposition of the random restriction method
Suresh Venkat
# A good exposition of the random restriction method

(Asked by: username_0 on 2014-06-04)

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.

**Tags:** cc.complexity-theory, reference-request, circuit-complexity

---

## 1 answers

### Answer by username_1 on 2014-06-04. Score: 9 | Accepted answer

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](http://www.math.rutgers.edu/~sk1233/courses/topics-S13/lec2.pdf) from Swastik Kopparty's class in Rutgers.


---

