CSCI 6114: Computational Complexity (Grad, Fall 2023)

Syllabus

Student hours for this class: Tuesdays 1:30-2:30 US Mountain Time, at my zoom link

Online Resources

• Complexity Zoo
• TCS StackExchange
• ECCC (like arXiv's cs.CC and cs.DS categories, but higher-quality; people often cross-post here and arXiv)
• arXiv cs.CC and cs.DS
• DBLP
• Prof. Grochow's Mind Map of (part of) Complexity - for helping explore & pick class topics

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

• Wigderson. Mathematics & Computation: A theory revolutionizing technology and science (pdf draft available at link)
• Hemaspaandra & Ogihara. The Complexity Theory Companion. Available digitally through CU libraries here
• Selman (editor). Complexity Theory Retrospective.
• Schöning and Pruim. Gems of Theoretical Computer Science

Some good textbooks

• Arora & Barak. Computational Complexity: A Modern Approach (the draft pdf from their website is fine)
• Du & Ko. Theory of Computational Complexity.
• Jukna. Boolean Function Complexity: Advances and Frontiers (focus on circuit complexity)
• Köbler, Schöning, and Torán, The Graph Isomorphism Problem: Its Structural Complexity. Even though it is focused on GI, it covers a fair bit of just general complexity, including oracles, PH, circuits, randomized classes, interactive proofs, and more.
• For more math behind Graph Isomorphism, check out Lauri & Scapellato, Topics in Graph Automorphisms and Reconstruction
• Some less advanced but really excellent textbooks whose later chapters might make appearances in this class: Sipser Ch. 8-10; Moore & Mertens Ch. 8,10,11; Homer & Selman Ch. 5,7-12

Problem Sets

• Problem Set 1: Circuits and P/poly
• Problem Set 2: the polynomial hierarchy PH
• Problem Set 3: More on PH
• Problem Set 4: Lower bounds by counting
• Problem Set 5: Diagonalization
• Problem Set 6: Oracles
• Problem Set 7: Oracles & circuits
• Problem Set 8: Graph isomorphism
• Problem Set 9: Randomized complexity
• Problem Set 10: Graph Isomorphism NP-complete implies PH collapses

Additional exercises

• Exercises on reductions

Final project topics

(Project topics posted w/ permission of their authors, in alphabetical order by last name)

• Adithya Bhaskara: Ladner's Theorem
• Matthew Fox: Blum complexity measures
• Elias Lindgren: Complexity of the Hajós calculus and connection to Frege systems
• Ben Little: Machine-Verifiable Proofs in Complexity Theory
• Gülce Kardeş: Fourier analysis of Boolean functions and the Linial-Mansour-Nisan Theorem
• Mary Monroe: TFNP, PPAD, and Nash Equilibrium
• Wilson Wu: Algebraic & geometric complexity theory