Computational Complexity Theory - Winter 2015

Two similar courses will be run simultaneously, one for UG students and another for PG students.

UG Course

Credits: 4
Pre-requisites: Algorithms, Discrete Maths, Theory of Computing

Post-conditions: Upon successful completion of the course, the student will gain the following:
  • knowledge of different models of computation and their relationships

  • ability to bound resource usage (e.g., time, space, circuit size, depth) required for problems under different models of computation

  • ability to place a problem in the hierarchy of computational complexity classes

  • ability to show separations, collapses of classes and prove completeness of problems

  • understand the major questions (e.g., P =? NP) and their role in other fields of computer science
PG Course

Credits: 4
Pre-requisites: Algorithms, Discrete Maths, Theory of Computing, Probability

Post-conditions: Upon successful completion of the course, the student will gain the following:
  • knowledge of different models of computation and their relationships

  • ability to bound resource usage (e.g., time, space, circuit size, depth) required for problems under different models of computation

  • ability to place a problem in the hierarchy of computational complexity classes

  • ability to show separations, collapses of classes and prove completeness of problems

  • understand the major questions (e.g., P =? NP) and their role in other fields of computer science

  • develop knowledge of randomized complexity classes and ability to perform randomized reductions

Description

Computational problems can be studied from the point of view of computational resources (e.g., running time) required to solve them – this forms the notional of computational difficulty. Apart from the nature of the problem, the difficulty also depends on the underlying model of computation. Problems can be related to each other based on their resource usage, and problems with similar difficulty can be grouped together to form a classification of computational problems into complexity classes.

Computational complexity is about studying the above concepts, and is especially concerned with giving precise upper and lower bound on the amount of resources required to solve certain problems. This has had a profound impact on current algorithm design and cryptography, and still sees applications in areas outside of theoretical computer science.

Instruction

Lectures will follow a mixture of regular lectures and flipped-classroom model. Hence, maturity in logic and reasoning is mandatory. The course will start where a standard course on Theory of Computation ends, hence it is strongly advisable that students are comfortable and strong in TOC.

Book

  • [S] Michael Sipser, “Introduction to the Theory of Computation”
  • [AB] Sanjeev Arora and Boaz Barak. “Complexity Theory: A Modern Approach”
Evaluation: 75% exams, 25% course-work and home-work
  • 40% final exam
  • 30% mid-sem
  • 5% quiz
  • 25% homework

Tentative schedule

 Week Topics Chapter
 1Turing machine definition, variants S3 AB1 Lec01  Lec02
 2Turing machine contd. UTM, simulation of TMs
 S3 AB1 Lec03  Lec04
 3Palindrome lower bound. Linear speedup, Defining and relating complexity classes
Lec05 Lec06 Lec07
 4Inclusions and separations: Tally language, padding technique, time hierarchy theorem S9.1 AB2 AB3 Lec08 Lec09
 5Reductions, hardness and complete problems
 S7 AB2 Lec10 Lec11
 6Relativization, BGS
 S8 AB3 Lec12 Lec13
 7Space complexity
 S8 AB4 Lec14-15
 8Space complexity: PSPACE, L, NL
 S8 AB4 Lec16 Lec17
 9Polytime hierarchy, alternation S10, AB5 Lec19 Lec20
 10Circuit complexity
 S9 AB6 Lec21 Lec22 Lec23-24
 11Non-uniform complexity
 Lec25-26

Adv topics
(PG) Probabilistic complexity classes 
 S10

Advanced topics: counting complexity, interactive proofs, communication complexity
Subpages (1): Scribes