Group Study

Computational Complexity

Self-study course is on-going. Welcome to join us!
General Purpose and Statement

We start this study group to learn the basic concepts in Computational Complexity, and hopefully eventually touch the base of quantum computational complexity. We will basically follow some free materials found online. We encourage people at all levels to join us.

Study Plan
  • Text we are going to use: Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak.
    • Duration: May 27, 2015-Aug 5, 2015.
    • Lecture notes are available, also here.
    • Study form: meet almost every Wednesday afternoon around 3:30pm mountain time (USA) in CQuIC of UNM; people from elsewhere can participate through Polycom. Each week, there will be a voluteer to lead the discussion. If you cannot participate for the live discussion, you can still leave questions in the ICIQ Google+ community on those topics.
  • Schedule (discussion leaders not included):
    • May 27: Chapter I.1: The computational model — and why it doesn’t matter
    • June 3: Chapter I.2: NP and NP Completeness
    • June 10: DAMOP (no class)
    • June 17: Chapter I.5: The Polynomial Hierarchy
    • June 24: Chapter I.7.1-7.5: Randomized Computation I
    • July 1: Chapter I.7.1-7.5: Randomized Computation II
    • July 8: Chapter I.8: Interactive Proofs
    • July 15: Chapter I.9: The Complexity of Counting
    • July 22: Chapter II.14: Algebraic computational models (Analog Computation)
    • July 29: Chapter II.18: PCP and Hardness of Approximation
    • Aug 5: Quantum Computational Complexity (resource TBA)
  • To use the Polycom:
    • Contact moc.liamtoh@s0002i for the IP address of the Polycom.
    • Install the Polycom client on your local computer: You should be able to find some Telepresence clients on your own for desktops/laptops/tablets or small phones running different OS's. Polycom company only provides comercial ones but you can use the trial version for free in the short period.
Forum for discussions at any time:
Extra learning materials:

There is a free course website on Complexity theory stuffs, if you are interested and haven't noticed yet: http://www.complexityexplorer.org/. Funded by Santa Fe Institute and public donations. One tutorial on Introduction to Information Theory is leading by Seth Lloyd. From a brief skimming, the tutorial looks similar to Seth's earlier course on the same topic taught at MIT and available on their open-courseware.