CS 7805 — Complexity Theory
4 semester hoursGraduateLectureusually offered: fallOnlineOnline
Covers core topics in computational complexity, including NP-completeness, time and space complexity, polynomial hierarchy, circuit complexity, probabilistic computation, interactive proofs, and hardness of approximation. Moves to more advanced topics that may include lower bounds, pseudorandomness, cryptography, and communication complexity.
Prerequisites
- CS 7800 (min C-)
Offering history
| Term | Sections | Enrolled | Capacity | Full | Open seats/section |
|---|---|---|---|---|---|
| Spring 2024 | 1 | 6 | 20 | 30% | 14.0 |
| Fall 2024 | 1 | 4 | 10 | 40% | 6.0 |
| Fall 2025 | 1 | 3 | 15 | 20% | 12.0 |
Snapshots from scheduled scrapes — not live seat availability. "Full" can exceed 100% when sections over-enroll.
Meeting times
Share of recent sections by weekday: M 0% · T 0% · W 0% · Th 0% · F 0%
Common patterns: async (100% of sections) — in patterns, R means Thursday
Professors
Fall
- Emanuele Viola (100% of students) · reviews
Spring
- Emanuele Viola (100% of students) · reviews
Percentages are each professor's average share of the season's enrolled students in recent terms.
Links
Official catalog (CS course descriptions) · Student reviews on RateMyHusky · All CS courses · Plan it at numap.app