Mathematics and computation : a theory revolutionizing technology and science
Wigderson, Avi
Mathematics and computation : a theory revolutionizing technology and science by Avi Wigderson - New Jersey : Princeton University Press, ©2019 - xiii, 418p. ; 26 cm.
Include bibliographical references.
1. Introduction 2. Prelude: Computation, undecidability, and limits to mathematical knowledge 3. Computational complexity 101: The basics, P, and NP 4. Problems and classes inside (and around) NP 5. Lower bounds, Boolean circuits, and attacks on P vs. NP 6. Proof complexity 7. Randomness in computation 8. Abstract pseudo-randomness 9. Weak random sources and randomness extractors 10. Randomness and interaction in proofs 11. Quantum computing 12. Arithmetic complexity 13. Interlude: Concrete interactions between math and computational complexity 14. Space complexity: Modeling limited memory 15. Communication complexity: Modeling information bottlenecks 16. On-line algorithms: Coping with an unknown future 17. Computational learning theory, AI, and beyond 18. Cryptography: Modeling secrets and lies, knowledge and trust 19. Distributed computing: Coping with asynchrony 20. Epilogue: A broader perspective of ToC
9780691189130
Computational complexity
Computer science -- Mathematics
511.3 / WIG-M
Mathematics and computation : a theory revolutionizing technology and science by Avi Wigderson - New Jersey : Princeton University Press, ©2019 - xiii, 418p. ; 26 cm.
Include bibliographical references.
1. Introduction 2. Prelude: Computation, undecidability, and limits to mathematical knowledge 3. Computational complexity 101: The basics, P, and NP 4. Problems and classes inside (and around) NP 5. Lower bounds, Boolean circuits, and attacks on P vs. NP 6. Proof complexity 7. Randomness in computation 8. Abstract pseudo-randomness 9. Weak random sources and randomness extractors 10. Randomness and interaction in proofs 11. Quantum computing 12. Arithmetic complexity 13. Interlude: Concrete interactions between math and computational complexity 14. Space complexity: Modeling limited memory 15. Communication complexity: Modeling information bottlenecks 16. On-line algorithms: Coping with an unknown future 17. Computational learning theory, AI, and beyond 18. Cryptography: Modeling secrets and lies, knowledge and trust 19. Distributed computing: Coping with asynchrony 20. Epilogue: A broader perspective of ToC
9780691189130
Computational complexity
Computer science -- Mathematics
511.3 / WIG-M