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.


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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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