Instructor:
Debrup
Chakraborty (debrup(AT)cs.cinvestav.mx)

References:
1) Computational
Complexity:
A modern approach, Sanjeev
Arora and Boaz Barak. (Text book, we shall
refer as Arora-Barak)

2) Computational
Complexity:
A conceptual perspective, Oded
Goldreich

Classes:
Monday and Wednesday from 10:00-12:00

Grading:
Home works
(60%),
2 Tests (40%)

Home work 2 (due July 24) Home work 3 (Due Aug 17)

classes; NP completeness; Reductions; Examples of NP complete problems; Diagonalization and

Relativization, Ladner’s theorem, oracle Turing machines; Space complexity; Boolean circuits and

non-uniform models of computation; Randomization, randomized complexity classes, examples

of randomized algorithms; Interactive proof systems; Probabilistic checking of proofs and the PCP

theorem.

Schedule (to be filled up as we proceed)

8th May Introduction

10th May No class: Mothers day

15th May Models of Computation:

why the alphabet size or number of tapes does not matter. Arora- Barak 1.1-1-3

17th May Turing Machines: Encoding Turing Machines with strings. Universal Turing Machines. A theorem about the slow down of a Universal Turing machine when simulating another machine.

Diagonalization: Some facts about infinite sets. Cantors proof of the fact that real numbers are not countable. Discussion on hierarchies of infinity and the continuum hypothesis

Computability: Discussions on the fact that there exists functions which are not computable. The function UC and the proof that it is not computable.

Arora-Barak 1.4, 1.5. Additional readings: A note about infinite sets. Some more links about infinite sets.

22May Computability: There exist more functions from strings to strings than Turing machines. The halting problem.

Some historical facts involving computability theory: Hilbert's 2nd, 10th and the Entscheidungsproblem, Godel's incompleteness theorems, Results of Turing and Church. The Church-Turing

Thesis.

Arora-Barak 1.5. Additional readings/viewings: Hilbert's Problems, Entscheidungsproblem, Godel's incompleteness theorems, The documentary "Dangerous Knowledge"

24May Basic Complexity Classes: DTIME, NTIME, P, NP, coNP, EXP, NEXP

29th May Reductions and NP completeness: Polynomial time reductions. Karp reductions and Cook reductions. NP completeness. Search problems, NP relations and self reducibility.

Arora-Barak 2.2, 2.5. Goldreich's notes

4th Jun Cooks Theorem: CNF formulas, CNF formulas can represent any Boolean function, Oblivious Turing machines, proof of Cooks theorem.

Arora-Barak 2.3.

6th Jun More reductions: 3SAT, CLIQUE, INDEPENDENT SET, VERTEX COVER are NP complete. coNP completeness, TAUTOLOGY is coNP complete.

Arora-Barak 2.4, 2.6

12th Jun Diagonalization: Deterministic and non-deterministic time hierarchy theorems, Ladner's theorem.

Arora-Barak 3.1, 3.2, 3.3 Additional readings from Lipton's Blog: On NP intermediate problems, On Diagonalization

14th Jun Diagonalization and Relativization: Oracle Turing machines, Baker-Gill-Solovay Theorem, discussion on relativization and why the BGS theorem is considered as a barrier

in settling the P vs NP question. Informal discussions about other attempts and known barriers for solving the P vs NP question.

Arora-Barak 3.4. Additional readings: Lipton's opinion on oracle results, a contrary opinion of Lance Fortnow, about the status of the P vs NP question by Fortnow

19th Jun A quick revision of what has been done till date.

Introduction to Space complexity: The classes SPACE, NSPACE, PSPACE, NPSPACE, L, NL

Arora-Barak 4.1. Additional readings: The post mentioned by Thomaz in class

21st Jun Configuration graphs of Turing Machines: Configuration graphs of space bounded machine, size of a configuration of a space s(n) machine, SPACE(s(n))= DTIME

(2^{O(s(n)), Savitch's theorem.

Arora-Barak 4.1, 4.2.1

26th Jun PSPACE completeness: PSPACE complete problems, quantified Boolean formulas, TQBF is PSPACE complete, winning strategies in games, the formula game.

Arora-Barak 4.2

28th Jun No Class (Turing Symposium)

5th July L and NL : Implicit log space computable functions, log-space reductions, NL completeness, PATH is NL complete. Certificate based definition of NL, Statement of Immerman

Szelepecsenyi Thm: NSPACE(s(n)) = coNSPACE(s(n))

Arora-Barak 4.3

6th July Polynomial Hierarchy: The classes , PH; Properties of polynomial hierarchy; complete problems in all levels of PH.

Arora-Barak 5.1, 5.2

10th July Polynomial Hierarchy: Oracle based definitions.

Arora-Barak 5.5

12th July Boolean Circuits: Definitions, the class P/poly, Turing machines which take advice, P uniform and log space uniform circuits. Statements of Karp Lipton and Meyers theorems.

Arora-Barak 6

16th July Revision

17th July Test1

24th July Boolean Circuits: Classes NC and AC.

Arora-Barak 6

26th July Probalbilistic Computations: Randomized Turing machines. The classes RP, BPP and ZPP. Error boosting in RP and BPP. ZPP and algorithms with expected

poly time. Arora-Barak 7

31st July Probabilistic Computations: BPP in P/poly. BPP in \sigma_2^p. Randomized reductions.

Arora-Barak 7

2nd Aug Interactive proofs: Proof as an interaction. Alternative view of NP. The classes IP and AM. Interactive proof for Graph non Isomorphism.

Arora-Barak 8 Additional readings: A brief history of the PCP theorem (this document traces the history of development of interactive proofs)