Credits: 4Pre-requisites: Algorithms, Discrete Maths, Theory of Computing, ProbabilityPost-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
- (if time & scope permits) develop knowledge of randomized complexity classes and ability to perform randomized reductions
## DescriptionComputational 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. Paper Reading: - On time versus space by Hopcroft, Paul, Valiant (1977) by
**Varun Ramanathan on Oct 25** - Improved Simulation of Nondeterministic Turing Machines by Kalyanasundaram, Lipton, Regan, Shokrieh (except Sec-5)
- One-Tape, Off-Line Turing Machine Computations by F.C. Hennie
Information and Control 8, 1965 (Sec-2 is optional) presented by**Siddhartha Jain, Hanit Banga on Oct 1** __The Fastest and Shortest Algorithm for All Well-Defined Problems__by Marcus Hutter (2002) (Sec-6,7 can be excluded)- The Minimum Equivalent DNF Problem and Shortest Implicants (leave out approximation-related results) by Christopher Umans
- A note on succinct representations of graphs by Christos H.Papadimitriou, Mihalis Yannakakis by
**Sushant Singh** __Circuit size is nonlinear in depth__by M.S.Paterson, L.G.Valiant by**Niket Singh**__Some Complexity Questions Related to Distributed Computing__by Andrew Yao (sec-3 can be skipped) by**Parth Mittal on 1st Nov**__On the degree of boolean functions as real polynomials__by Noam Nisan (https://doi.org/10.1145/129712.129757)__The Multiplicative Complexity of 6-variable Boolean Functions__by Calik, Turan and Peralta (https://eprint.iacr.org/2018/002.pdf) - upto Sec-3
| ## InstructionLectures 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 - [AB] Sanjeev Arora and Boaz Barak. “Complexity Theory: A Modern Approach”
- (Reference) [S] Michael Sipser, “Introduction to the Theory of Computation”
Evaluation: 75% exams, 25% course-work and home-work- 40% final exam
- 30% mid-sem
- 5% quiz / scribe (see below)
- 18% homework (1% for each homework problem, lowest 15% problems to be dropped)
- 5% paper reading (to be decided after mid-sem exam)
- 2% - free (thanks for attending the course)
Tentative schedule
Scribe instructions Try to present the results as reusable lemma/theorem/etc. and use figures if that improve clarity (use ipe/xfig/etc. pdf-producing WYSIWIG tools). |

### Computational Complexity Theory - Monsoon 2018

Subpages (1):
Scribes