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.


1 Answer 1


I recommend looking at Stasys Jukna's books Extremal Combinatorics and Boolean Function Complexity. For discrepancy and the like, you can look at Bernard Chazelle's book The Discrepancy Method (available online at his homepage).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.