Cover Image

Mathematics and computation : a theory revolutionizing technology and science /

Bibliographic Details
Main Author: Wigderson, Avi (Author)
Corporate Author: JSTOR (Organization)
Format: eBook
Language:English
Published: Princeton, New Jersey : Princeton University Press, [2019]
Subjects:
Computational complexity.
Algebra, Boolean.
Cryptography.
Electronic books.
Online Access:Connect to the full text of this electronic book
Table of Contents:
  • Introduction
  • Prelude: computation, undecidability, and limits to mathematical knowledge
  • Computational complexity 101: the basics, P, and NP
  • Problems and classes inside (and around) NP
  • Lower bounds, Boolean circuits, and attacks on P vs NP
  • Proof complexity
  • Randomness in computation
  • Abstract pseudo-randomness
  • Weak random sources and randomness extractors
  • Randomness and interaction in proofs
  • Quantum computing
  • Arithmetic complexity
  • Interlude: concrete interactions between math and computational complexity
  • Space complexity: modeling limited memory
  • Communication complexity: modeling information bottlenecks
  • On-line algorithms: coping with an unknown future
  • Computational learning theory, AI, and beyond
  • Cryptography: modeling secrets and lies, knowledge and trust
  • Distributed computing: coping with asynchrony
  • Epilogue: a broader perspective of ToC.