Derrick Stolee
J. L. Doob Research Assistant Professor
Department of Mathematics
University of Illinois at Urbana-Champaign

Home

Teaching

Papers

Presentations

Software

Other

 CSCE 424/824 - Computational Complexity Theory

Spring 2012

Room: CBA 306 Instructors: Derrick Stolee Steve Goddard
Time: TR 9:30--10:45am Office: Avery 336 Avery 267
Office Hours: MW 2:00--3:30pm Email: s-dstolee1@math.unl.edu goddard@cse.unl.edu
Textbook: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak

Syllabus

Course Goals

We will discuss the fundamentals of computational complexity theory as well as investigate some of the recent results on the edges of current research. The course shall begin by discussing the {\it core topics} of complexity theory. From this base of fundamental knowledge, we shall venture into {\it special topics} based on student preference. The topics are listed below.

Core Topics: These topics will be discussed in sequential order.

  • Chapter 1: The computational model.
  • Chapter 2: NP and NP-completeness.
  • Chapter 3: Diagonalization.
  • Chapter 4: Space complexity.
  • Chapter 5: The polynomial hierarchy and alternations.
  • Chapter 6: Boolean circuits.
  • Chapter 7: Randomized computation.

Special Topics: These topics will be discussed in order of student preference.

  • Chapter 8: Interactive proofs.
  • Chapter 11: PCP theorem and hardness of approximation.
  • Chapter 12: Decision trees.
  • Chapter 13: Communication Complexity.
  • Chapter 14: Circuit lower bounds.
  • Chapter 17: Complexity of counting.
  • Chapter 19: Hardness amplification and error-correcting codes.
  • Chapter 20: Derandomization.
  • Chapter 21: Pseudorandom constructions: Expanders and extractors.

Students are expected to meet with the instructor to discuss preferences for the special topics. These meetings will be requested near the end of the discussions of core topics.