CS747 - Randomized Methods in Computational Complexity (Sem I, 2023-24)

 

Links


Books, LectureS

Youtube, Lecture videos edited by NPTEL.
Course, Randomized methods in Computational Complexity, Nitin Saxena.
Book, Complexity Theory: A Modern Approach, Sanjeev Arora and Boaz Barak.
Book, Computational Complexity: A Conceptual Perspective, Oded Goldreich.

Online Stuff

Pseudorandomness
Complexity Zoo, Scott Aaronson.

History: Turing.


------------------------------------------------------
``Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method.''

-- John von Neumann in Monte Carlo Method (1951) .