CSE P 590B Project

Spring 2006


The purpose of the project is to read original papers of some importance from the computational complexity literature and explain the results in a 20 minute talk at the end of the quarter.  Some of these papers are quite difficult, and others are covered somewhat thoroughly in class.  If you choose to work as a team of two, the talk will be 40 minutes.


1. NP-completeness



2. Randomized Computation



3. The Polynomial-Time Hierarchy



4. Interactive Proofs



5. Public-Coin Interactive Proofs



6. Zero-Knowledge Proofs



7. Probabilistic Checkable Proof (PCP)



8. Hardness of Approximation



9. Circuit Depth and Space Complexity



10. #P Complexity



11. Non-Uniform Polynomial Time



12. Polynomial Space



13. Relativization



14. Complexity of Logic



15. Information Complexity



16. Quantum Computing



17. History of Computing