Browse
Publications
Preprints
About
About UCL Open: Env.
Aims and Scope
Editorial Board
Indexing
APCs
How to cite
Publishing policies
Editorial policy
Peer review policy
Equality, Diversity & Inclusion
About UCL Press
Contact us
For authors
Information for authors
How it works
Benefits of publishing with us
Submit
How to submit
Preparing your manuscript
Article types
Open Data
ORCID
APCs
Contributor agreement
For reviewers
Information for reviewers
Review process
How to peer review
Peer review policy
My ScienceOpen
Sign in
Register
Dashboard
Search
Browse
Publications
Preprints
About
About UCL Open: Env.
Aims and Scope
Editorial Board
Indexing
APCs
How to cite
Publishing policies
Editorial policy
Peer review policy
Equality, Diversity & Inclusion
About UCL Press
Contact us
For authors
Information for authors
How it works
Benefits of publishing with us
Submit
How to submit
Preparing your manuscript
Article types
Open Data
ORCID
APCs
Contributor agreement
For reviewers
Information for reviewers
Review process
How to peer review
Peer review policy
My ScienceOpen
Sign in
Register
Dashboard
Search
45
views
0
references
Top references
cited by
120
Cite as...
0 reviews
Review
0
comments
Comment
0
recommends
+1
Recommend
0
collections
Add to
0
shares
Share
Twitter
Sina Weibo
Facebook
Email
1,596
similar
All similar
Record
: found
Abstract
: not found
Book
: not found
Computational Complexity
monograph
Author(s):
Sanjeev Arora
,
Boaz Barak
Publication date
(Online):
2009
Publisher:
Cambridge University Press
Read this book at
Publisher
Buy book
Review
Review book
Invite someone to review
Bookmark
Cite as...
There is no author summary for this book yet. Authors can add summaries to their books on ScienceOpen to make them more accessible to a non-specialist audience.
Related collections
Computational epistasis
Author and book information
Book
ISBN:
9780511804090
Publication date (Print):
2009
Publication date (Online):
2009
DOI:
10.1017/CBO9780511804090
SO-VID:
6d333bb6-13c5-4bc0-8c23-cebe2118dbbe
History
Data availability:
Comments
Comment on this book
Sign in to comment
Book chapters
pp. xiii
About this book
pp. xix
Introduction
pp. 1
Notational conventions
pp. 9
The computational model – and why it doesn't matter
pp. 38
NP and NP completeness
pp. 68
Diagonalization
pp. 78
Space complexity
pp. 95
The polynomial hierarchy and alternations
pp. 106
Boolean circuits
pp. 123
Randomized computation
pp. 143
Interactive proofs
pp. 172
Cryptography
pp. 201
Quantum computation
pp. 237
PCP theorem and hardness of approximation: An introduction
pp. 259
Decision trees
pp. 270
Communication complexity
pp. 286
Circuit lower bounds: Complexity theory's Waterloo
pp. 307
Proof complexity
pp. 318
Algebraic computation models
pp. 341
Complexity of counting
pp. 361
Average case complexity: Levin's theory
pp. 373
Hardness amplification and error-correcting codes
pp. 402
Derandomization
pp. 421
Pseudorandom constructions: Expanders and extractors
pp. 460
Proofs of PCP theorems and the Fourier transform technique
pp. 498
Why are circuit lower bounds so difficult?
pp. 508
Appendix: Mathematical background
pp. 531
Hints and selected exercises
pp. 545
Main theorems and definitions
pp. 549
Bibliography
Similar content
1,596
A mixed-methods framework for analyzing text data: Integrating computational techniques with qualitative methods in demography
Authors:
Parijat Chakrabarti
,
Margaret Frye
Gformula: Estimating Causal Effects in the Presence of Time-Varying Confounding or Mediation using the G-Computation Formula
Authors:
Rhian Daniel
,
Bianca L. De Stavola
,
Simon Cousens
Computationally Designed Armadillo Repeat Proteins for Modular Peptide Recognition
Authors:
Fabio Parmeggiani
,
Christian Reichen
,
Simon Hansen
…
See all similar
Cited by
111
Noisy intermediate-scale quantum algorithms
Authors:
Kishor Bharti
,
Alba Cervera-Lierta
,
Thi Kyaw
…
Simulating Chemistry Using Quantum Computers
Authors:
Ivan Kassal
,
James D. Whitfield
,
Alejandro Perdomo-Ortiz
…
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Authors:
Michael Bremner
,
Richard Jozsa
,
Dan Shepherd
See all cited by