# CS6840 Computability and Complexity

## Sep - Dec 2020

### Coordinates

- Where: Online
- When: A slot (Mon: 8 - 8.50; Tue: 12 - 12.50; Thu: 11 - 11.50; Fri: 10 - 10.50)

### Objectives

This course builds on the topics covered in CS2200 - Languages, Machines and Computation as we delve deeper into computability theory and complexity theory. The aim of the course is to introduce the rich structural theory of computability and complexity. This course is a starting point for more advanced courses in theoretical computer science. In particular, this course is a strict pre-requisite for CS6840 - Modern Complexity Theory offered in the even semesters.

### Contents

The following is a brief overview of the topics that will be covered in this course. The order of the topics covered may vary.

**Computability theory**- Turing machines, undecidability, Arithmetic and analytical hierarchy, Recursion theorem, Incompleteness theorem.**Complexity theory**- Time complexity, Space complexity, Hierarchy theorems, Randomized complexity and interactive proofs, Counting complexity.

### References

**[K1]**: *Automata and Computability* - *Dexter C. Kozen*

**[K2]**: *Theory of Computation* - *Dexter C. Kozen*

**[AB]**: *Computational Complexity: A Modern Approach* - *Sanjeev Arora* and *Boaz Barak*

**[DK]**: *Theory of Computational Complexity* - *Ding-Zhu Du* and *Ker-I Ko*

There are a large number of lecture notes and resources available online, which we will refer to during the course.

### Grading policy

Assignments: 40%

Scribing: 10%

Course reading: 10%

Mid-sem: 10%

End-sem + viva: 30%

### Important dates

Problem Sets (deadlines): Sep 18, Oct 2, Oct 16, Oct 30, Nov 15, Nov 29

Mid-sem: Oct 20

End-sem: Dec 15