joshuagrochow 43d2b3b081 | ||
---|---|---|
README.md |
README.md
Spring 2024 Reading Group: Machine-independent complexity and formalization in theorem-provers ("Logic & Complexity" for short)
CU Boulder CS Theory
When: Mondays 1:20pm-2:20pm US Mountain Time (click for time zone conversion)
Where: Zoom (link available for participants only)
Prerequisites: some knowledge of complexity theory. Having taking an undergrad or grad course in computational complexity would certainly suffice, but isn't strictly necessary. But definitely more complexity theory than the one week typically seen in an Intro Algorithms course.
We are open to participants with the above background and legitimate interest from anywhere. We currently have participants from CU Boulder (both Theory and PLV), U. Maryland, ENS France, UIUC, and BITS Pilani. Please contact Prof. Grochow if you're interested in joining!
Many of the topics are independent from one another; where there are dependencies we've indicated that in the schedule. If you missed a session or are joining mid-semester, past sessions are recorded and available privately for participants.
Schedule:
- 29 Jan 2024: Intro to first-order logic (with a view towards descriptive complexity) (Josh Grochow) (Resource: Descriptive Complexity by Immerman, Sections 1.1 and 1.4)
- 5 Feb 2024: Blum's Axioms (Matthew Fox)
- 12 Feb 2024: A Short Introduction to Implicity Computational Complexity by Ugo Dal Lago (Lucy Pipkorn)
- 19 Feb 2024: Some results in descriptive complexity (Ben Little) (Will assume the 1/29 talk as background)
- 26 Feb 2024: [RESCHEDULED due to illness]
- 4 Mar 2024: Intro to Lean (Tarek Tohme, ENS) (Resources: Patrick Massot's Glimpse of Lean, see Learning Lean 4 for more)
- 11 Mar 2024: Formalizing Turing machines in Lean (Jon Z. Cai) (will assume the previous week as background)
- 18 Mar 2024: Discussion session
- 25 Mar 2024: NO MEETING (Spring Break)
- 1 Apr 2024: Cancelled
- 8 Apr 2024: Quantum Computation as Geometry by Nielsen, Dowling, Gu, & Doherty (arXiv) (Matthew Fox)
- 15 Apr 2024: Accattoli & Dal Lago. Beta Reduction is Invariant, Indeed (Lucy Pipkorn)
- 22 Apr 2024: Realizability theory
- 29 Apr 2024: Type-enforced polynomial-time computation (will assume previous week's talk as background)
- 6 May 2024: One Complexity Theorist's View of Quantum Computing by Fortnow (arXiv)