CS 277. Concrete Complexity
Catalog Description: The study of inherent complexity of specific computational problems. Circuit complexity, branching programs, decision tree models, sorting and selection, evasive graph properties, algebraic complexity, communication complexity, VLSI complexity, time/space trade-offs.
Units: 3
Prerequisites: 170 and Mathematics 113A.
Formats:
Fall: 3 hours of lecture per week
Spring: 3 hours of lecture per week
Grading basis: letter
Final exam status: Written final exam conducted during the scheduled final exam period