Computational complexity (Record no. 664)

000 -LEADER
fixed length control field 02641nam a2200229Ia 4500
003 - CONTROL NUMBER IDENTIFIER
control field OSt
005 - DATE AND TIME OF LATEST TRANSACTION
control field 20241122112247.0
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION
fixed length control field 170804s2009 xx 000 0 und d
020 ## - INTERNATIONAL STANDARD BOOK NUMBER
International Standard Book Number 9780521424264
040 ## - CATALOGING SOURCE
Original cataloging agency ICTS-TIFR
050 ## - LIBRARY OF CONGRESS CALL NUMBER
Classification number QA267.7
100 ## - MAIN ENTRY--PERSONAL NAME
Personal name Sanjeev Arora
245 ## - TITLE STATEMENT
Title Computational complexity
Remainder of title : a modern approach
260 ## - PUBLICATION, DISTRIBUTION, ETC.
Name of publisher, distributor, etc. Cambridge University Press,
Date of publication, distribution, etc. [c2009]
Place of publication, distribution, etc. U.K.:
300 ## - Physical Description
Pages: 579 p.
505 ## - FORMATTED CONTENTS NOTE
Formatted contents note 0 - Notational conventions <br/><br/>PART ONE - BASIC COMPLEXITY CLASSES <br/>1 - The computational model – and why it doesn't matter <br/>2 - NP and NP completeness <br/>3 - Diagonalization <br/>4 - Space complexity <br/>5 - The polynomial hierarchy and alternations <br/>6 - Boolean circuits <br/>7 - Randomized computation <br/>8 - Interactive proofs <br/>9 - Cryptography <br/>10 - Quantum computation <br/>11 - PCP theorem and hardness of approximation: An introduction <br/><br/>PART TWO - LOWER BOUNDS FOR CONCRETE COMPUTATIONAL MODELS <br/>12 - Decision trees <br/>13 - Communication complexity <br/>14 - Circuit lower bounds: Complexity theory's Waterloo <br/>15 - Proof complexity <br/>16 - Algebraic computation models <br/><br/>PART THREE - ADVANCED TOPICS <br/>17 - Complexity of counting <br/>18 - Average case complexity: Levin's theory <br/>19 - Hardness amplification and error-correcting codes <br/>20 - Derandomization <br/>21 - Pseudorandom constructions: Expanders and extractors <br/>22 - Proofs of PCP theorems and the Fourier transform technique <br/>23 - Why are circuit lower bounds so difficult?
520 ## - SUMMARY, ETC.
Summary, etc. This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the field and progresses to advanced results. Contents include: definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, interactive proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complexity, constant depth, algebraic and monotone circuits, proof complexity), average-case complexity and hardness amplification, derandomization and pseudorandom constructions, and the PCP theorem. --- summary provided by publisher
650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical term or geographic name entry element Algorithmics
650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM
Topical term or geographic name entry element Computational Geometry
700 ## - ADDED ENTRY--PERSONAL NAME
Personal name Boaz Barak
942 ## - ADDED ENTRY ELEMENTS (KOHA)
Source of classification or shelving scheme
Koha item type Book
Holdings
Withdrawn status Lost status Damaged status Not for loan Collection code Home library Shelving location Date acquired Full call number Accession No. Koha item type
          ICTS Rack No 5 01/19/2017 QA267.7 00664 Book