Mathematics and Computation
This lecture note covers the following
topics, Prelude, computation, undecidability and the limits of mathematical
knowledge, Computational complexity 101, the basics, Problems and classes inside
N P, Lower bounds, Boolean Circuits, and attacks on P vs. NP, Proof complexity,
Randomness in computation, Abstract pseudorandomness, Weak random sources and
randomness extractors, Randomness in proof, Randomness in proofs, Arithmetic
complexity, Interlude, Concrete interactions between Math and Computational
Complexity.
Author(s): Avi Wigderson
372 Pages