Computer Science 741 - Complexity Theory

The study of the resources required to solve problems in various models of computation. Sequential computation: Turing machines, non-determinism, alternation, algebraic automata theory. Parallel computation: Boolean circuits, branching programs, uniformity, lower bounds for circuit models. Descriptive complexity. Possible optional topics depending on student interest: approximation of NP-complete problems, interactive proofs, nonuniform finite automata, dynamic complexity.

Open to Graduate students only. COMPSCI 601 STUDENTS NOT MEETING PREREQUISITE WITH INSTRUCTOR PERMISSION. STUDENTS NEEDING SPECIAL PERMISSION MUST REQUEST OVERRIDES VIA THE ON-LINE FORM: https://www.cics.umass.edu/overrides.