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.

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

Class homepage on inst.eecs