Borrow it
Coverart for item
The Resource Mathematics and computation: : a theory revolutionizing technology and science, Avi Wigderson

Mathematics and computation: : a theory revolutionizing technology and science, Avi Wigderson

Creator
Summary
"An introduction to computational complexity theory, its connections and interactions with mathematics, and its central role in the natural and social sciences, technology, and philosophy, Mathematics and Computation provides a broad, conceptual overview of computational complexity theory--the mathematical study of efficient computation. With important practical applications to computer science and industry, computational complexity theory has evolved into a highly interdisciplinary field, with strong links to most mathematical areas and to a growing number of scientific endeavors. Avi Wigderson takes a sweeping survey of complexity theory, emphasizing the field's insights and challenges. He explains the ideas and motivations leading to key models, notions, and results. In particular, he looks at algorithms and complexity, computations and proofs, randomness and interaction, quantum and arithmetic computation, and cryptography and learning, all as parts of a cohesive whole with numerous cross-influences. Wigderson illustrates the immense breadth of the field, its beauty and richness, and its diverse and growing interactions with other areas of mathematics. He ends with a comprehensive look at the theory of computation, its methodology and aspirations, and the unique and fundamental ways in which it has shaped and will further shape science, technology, and society."--
Language
eng
Work
Publication
Extent
xiii, 418 pages:
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
Isbn
9780691189130
Instance
Label
Mathematics and computation: : a theory revolutionizing technology and science
Title
Mathematics and computation:
Title remainder
a theory revolutionizing technology and science
Statement of responsibility
Avi Wigderson
Creator
Subject
Language
eng
Summary
"An introduction to computational complexity theory, its connections and interactions with mathematics, and its central role in the natural and social sciences, technology, and philosophy, Mathematics and Computation provides a broad, conceptual overview of computational complexity theory--the mathematical study of efficient computation. With important practical applications to computer science and industry, computational complexity theory has evolved into a highly interdisciplinary field, with strong links to most mathematical areas and to a growing number of scientific endeavors. Avi Wigderson takes a sweeping survey of complexity theory, emphasizing the field's insights and challenges. He explains the ideas and motivations leading to key models, notions, and results. In particular, he looks at algorithms and complexity, computations and proofs, randomness and interaction, quantum and arithmetic computation, and cryptography and learning, all as parts of a cohesive whole with numerous cross-influences. Wigderson illustrates the immense breadth of the field, its beauty and richness, and its diverse and growing interactions with other areas of mathematics. He ends with a comprehensive look at the theory of computation, its methodology and aspirations, and the unique and fundamental ways in which it has shaped and will further shape science, technology, and society."--
Assigning source
Provided by publisher
http://library.link/vocab/creatorName
Wigderson, Avi
Illustrations
illustrations
Index
no index present
Literary form
non fiction
Nature of contents
bibliography
http://library.link/vocab/subjectName
  • Computational complexity
  • Algebra, Boolean
  • Cryptography
Label
Mathematics and computation: : a theory revolutionizing technology and science, Avi Wigderson
Instantiates
Publication
Copyright
Bibliography note
Includes bibliographical references (pages 349-418)
Carrier category
volume
Carrier category code
  • nc
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
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
Control code
on1051136440
Dimensions
26 cm
Extent
xiii, 418 pages:
Isbn
9780691189130
Media category
unmediated
Media MARC source
rdamedia
Media type code
  • n
Other physical details
illustrations
System control number
(OCoLC)1051136440
Label
Mathematics and computation: : a theory revolutionizing technology and science, Avi Wigderson
Publication
Copyright
Bibliography note
Includes bibliographical references (pages 349-418)
Carrier category
volume
Carrier category code
  • nc
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
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
Control code
on1051136440
Dimensions
26 cm
Extent
xiii, 418 pages:
Isbn
9780691189130
Media category
unmediated
Media MARC source
rdamedia
Media type code
  • n
Other physical details
illustrations
System control number
(OCoLC)1051136440

Subject

Library Locations

    • Badia FiesolanaBorrow it
      Via dei Roccettini 9, San Domenico di Fiesole, 50014, IT
      43.803074 11.283055

Library Links

Structured data from the Bibframe namespace is licensed under the Creative Commons Attribution 4.0 International License by European University Institute Library. Additional terms may apply to data associated with third party namespaces.