<p>I recommend looking at <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/">Stasys Jukna</a>'s books Extremal Combinatorics and Boolean Function Complexity. For discrepancy and the like, you can look at <a href="http://www.cs.princeton.edu/~chazelle/">Bernard Chazelle</a>'s book The Discrepancy Method (available online at his homepage).</p>

CC BY-SA 3.0
2013-01-18T15:45:51.777Z
2013-01-18T15:45:51.777Z
Yuval Filmus
<p>I read the famous book by Alon and Spencer on the probabilistic method in combinatorics. </p>

<p>Is there a survey or lecture notes on recent advances and relationships with the following complexity theoretic topics of this method beyond this textbook?</p>

<ol>
<li><p>pseudorandom generators fooling concrete computation models, expander graphs.</p></li>
<li><p>complexity lower bounds for concrete computation models such as circuits, branching programs, streaming, property testing, learning, and communication complexity.</p></li>
<li><p>randomized complexity theoretic aspects of algebraic coding theory and information theory.</p></li>
<li><p>VC-dimension, discrepancy and other geometric topics.</p></li>
</ol>

<cc.complexity-theory><reference-request><co.combinatorics><soft-question><survey>
Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory
shen
# Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory

(Asked by: username_0 on 2013-01-18)

I read the famous book by Alon and Spencer on the probabilistic method in combinatorics.

Is there a survey or lecture notes on recent advances and relationships with the following complexity theoretic topics of this method beyond this textbook?

1. pseudorandom generators fooling concrete computation models, expander graphs.
2. complexity lower bounds for concrete computation models such as circuits, branching programs, streaming, property testing, learning, and communication complexity.
3. randomized complexity theoretic aspects of algebraic coding theory and information theory.
4. VC-dimension, discrepancy and other geometric topics.

**Tags:** cc.complexity-theory, reference-request, co.combinatorics, soft-question, survey

---

## 1 answers

### Answer by username_1 on 2013-01-18. Score: 6

I recommend looking at [Stasys Jukna](http://www.thi.informatik.uni-frankfurt.de/~jukna/)'s books Extremal Combinatorics and Boolean Function Complexity. For discrepancy and the like, you can look at [Bernard Chazelle](http://www.cs.princeton.edu/~chazelle/)'s book The Discrepancy Method (available online at his homepage).


---

