Computational Complexity

Parent resource - Computational Complexity

By Sanjeev Arora ISBN_13 9780521424264, ISBN_10 0521424267 New and classical results in computational complexity, including interactive proofs, PCP, derandomization, and quantum computation. Ideal for graduate students. About - Computational Complexity http://cse.iitkgp.ac.in/~spp/cc2021.html CS41103 COMPUTATIONAL COMPLEXITY L-T-P: 3-1-0, Credits: 4 (as in cse website) Computational Models (machine models, logic); Problems, computability, Algorithms, Resources, and Complexity; Turing machines (time and space bounds, nondeterminism); Logic (Boolean logic, circuits, first and second order logic); Complexity classes (hierarchy theorem, reachability, P, NP, Co-NP); Reduction and completeness; Randomized computation; Approximability; Cryptography and protocols; Parallel Computation; Polynomial Hierarchy; Logarithmic space; Polynomial space; Exponential time and space. References ========== Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Longman. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing. John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata, Languages and Computation, Addison-Wesley, 1979. J. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity, Volumes I and II, Springer. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach.

PAPERS

Journal papers etc relevant to this collection

No journal paper, dissertation or book chapter has been added by the curator to this collection yet.

PATENTS

Patents added to this collection

No patent document has been added by the curator to this collection yet.

Curated By

Sudebkumar Prasant Pal  

IIT Kharagpur

...

Contributors

People who have contributed to this collection

Workshops and Short Courses  

No short courses scheduled yet

Request a topic of interest.

A short course for this topic has not been currently scheduled. You may request a topic of interst that you would like this instructor to cover in the short course. Please follow this instructor to be notified when any of his or her short courses come online.

BOOKS

Books relevant to this collection

DOCUMENTS

Documents uploaded to this collection

No document has been added by the curator to this collection yet.

PAPERS

Journal papers etc relevant to this collection

No journal paper, dissertation or book chapter has been added by the curator to this collection yet.

BOOKS

Books relevant to this collection

VIDEOS

All videos in this lecture series

PATENTS

Patents added to this collection

No patent document has been added by the curator to this collection yet.

EXTERNAL RESOURCES

Webresorces for this collection

CMSC 652 --- Complexity Theory...