CSCE 424/824
(Spring 2010)-Complexity Theory
Certain computational problems such as Graph Reachability and Matching
admit very fast algorithms to solve them using a computer. On the
other hand problems like Boolean Formula Satisfiability and Traveling
Salesman Problem, till today, defy such fast solution. Complexity
theory investigates the reasons behind this important phenomenon.
This course will introduce students to the area of computational
complexity theory. We will focus on topics including complexity
classes, lower bounds, the role of randomness in computations. This
will be a theoretical course: we will take a pen-and-paper approach
and avoid computer implementations and other empirical studies. That
is, we establish results in the form of mathematical theorems.
The course is in the Theory Track.
Prerequisites
CSCE 235 and 310 are prerequisites for the course. In particular a
good knowledge of basic combinatorial techniques and probability
theory is necessary. Familiarity with algorithms (CSCE 423/823 or
equivalent) and automata theory (CSCE 428/828 or equivalent) are
recommended for understanding the course material faster. But students
with certain level of mathematical maturity will be able to make very
good use of the course without the knowledge of algorithms or
automata.
Textbook
We will mostly use the text book
Computational Complexity, A Mordern Approach by
Sanjeev Arora and Boaz Barak.
Instructors: Vinod Variyam and Derrick Stolee
Venue: 118, Avery Hall
Time : MWF 12:30pm - 1:20pm