To give the student further exposure to the classification of problems based on their computational requirements, and to mathematical tools designed to explore the structural consequences of such classifications.

Students are expected to have basic knowledge of complexity theory (P, NP,
NP-completeness).

References to be determined.

Three hours of lecture per week.

Relativization. Structure of NP. Alternation and the polynomial-time hierarchy. Interactive proof systems. Provably intractable problems. Feasible parallel computations, Boolean circuits, and the class NC.

Fixed-parameter tractability. Kernelization and bounded search trees. Relationship to optimization problems and approximation schemes. Parameterized reducibility and W[1]-completeness. The W-hierarchy.

Randomness and incompressibility. Robustness. Algorithmic complexity and algorithmic prefix complexity. Applications to computational complexity.

David R. Cheriton School of Computer Science

University of Waterloo

Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293

Fax: 519-885-1208

Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics