Anagha Gokul

Resources

Here are a few resources for (aspiring) theoreticians. None of the material linked on this page belong to me: full credits to the creators and authors. This page is dynamic. Mostly for my quick reference. Note to self: Too clustered, break it into pages.

Books, Papers and Lectures

Algebraic Complexity Theory

Lectures/Videos

  1. Lectures by Nitin Saxena on Arithmetic Circuit Complexity
  2. Bootcamp at DIMACS by Nutan Limaye

Surveys

  1. Surveys on PIT: PIT-1, PIT-2 (both by Saxena), 2024-Pranjal-Ghosh
  2. Lower Bounds: Survey by Ramprasad
  3. Algebraic Hardness vs Randomness by Kumar and Saptharishi
  4. For everything: Shpilka and Yehudayoff, a bit dated; but best for classical lower bounds and structural results.

Computational Complexity Theory

  1. Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak
  2. Theory of Computation: Michael Sipser
  3. The Electronic Colloquium on Computational Complexity for the latest papers in the field. (warning: clicking = downloading)
  4. Lectures on Computational Complexity Theory, Algebraic Complexity and Randomized Methods in Complexity available on NPTEL and STCS TIFR's YouTube channel
  5. Lecture notes on complexity by Luca Trevisan
  6. Mathematics and Computation by Avi Wigderson

Pseudorandomness

  1. Salil Vadhan's Monograph
  2. Lectures by STCS TIFR YouTube channel (2 offerings hosted online till date)
  3. Luca Trevisan's notes on Pseudorandomness and Combinatorial Constructions
  4. Expanders Survey by Hoory, Linial and Wigderson

Design and Analysis of Algorithms

  1. Algorithm Design: Jon Kleinberg and Éva Tardos
  2. Algorithms by Jeff Erickson
  3. Approximation Algorithms: Vijay V Vazirani
  4. Randomized Algorithms: Prabhakar Raghavan and Rajeev Motwani

Algebra (and computation)

  1. An assortment of lecture notes on various topics is maintained by Andrew Kobin
  2. Madhu Sudan's course notes on Algebra and Computation

Combinatorics

  1. Lectures on Additive Combinatorics by Tim Gowers hosted on his YouTube channel
  2. Terry Tao's book on Additive Combinatorics
  3. Yufei Zhao's notes on the Probabilistic Method
  4. The Probabilistic Method by Noga Alon and Joel Spencer
  5. Linear Algebra and Combinatorics by Babai and Frankl

Lectures and Miscellaneous Videos

Blogs. Podcasts and Websites

Websites of early-career researchers (and friends :) )

Here are a few websites of friends and early-career researchers that are a treasure trove for TCS research.