Picture of Joshua A. Grochow
Joshua A. Grochow
Assistant Professor
Departments of Computer Science and Mathematics
University of Colorado at Boulder
[first initial][last name]@colorado.edu
I will not be in the office during the coronavirus pandemic. My virtual office is here on Zoom.
Fax: (303) 492-2844 (ATTN: me)
CS Theory @ CU Boulder
Complex Systems @ CU Boulder

Me @ Mastodon BlueSky Twitter csthoery.SE mathoverflow ORCID
My pubs @ arXiv ECCC DBLP MathSciNet Google Scholar SciRate

CSCI 6114: Computational Complexity (Grad, Fall 2021)

Syllabus

Online Resources

Books

There is no textbook for this class, we will read selections from some subset of the books below, lecture notes, and research articles. However, regardless of what we cover in class, these books are great complexity resources! (When available through CU libraries the link below is to the CU Library Proxy that will log you in; if you don't want that look at the URL - it should be fairly clear how to modify it to not do that, or ask me for help)

Some of my favorite non-textbooks

Some good textbooks

In-Class Exercises

Classes 2-3: Circuits and P/poly
Classes 4-6: Polynomial Hierarchy PH
Class 6-8: Oracles, relativization, and the polynomial hierarchy
Class 9-11: Graph Isomorphism
Class 11-13: Weisfeiler—Leman
Class 14-16: Proof complexity
Classes 16-19: Algebraic proof complexity
Classes 20-23: Randomized complexity
Classes 24-26: PSPACE and IP

Final Projects

These projects were chosen by the students in the class, to be presented during the last two weeks of term:

Homework

Homework on Graph Isomorphism, due Thurs Oct 7