Theory of Computing

General Information

Grading

Dates and Deadlines

Homework 1 deadline: September 29, 2017, 23:59 AoE
Homework 1, Extra Problems deadline: October 6, 2017, before seminar
Homework 2 + Extra Problems deadline: November 3, 2017, before lecture
Homework 3 + Extra Problems deadline: November 24, 2017, before lecture
Homework 4 + Extra Problems deadline: December 17, 2017, 23:59 Moscow time, submit here

Colloquium

Date and time: December 11, 12:10
Room: 505
Program

Course Materials

Summary	Problem list
Complexity classes P, PSPACE, EXP. Time and space hierarchy theorems (see also Sipser Section 9.1)	Problem list 1
Complexity class NP. Examples. Inclusions between P, NP and EXP. Non-deterministic TMs. Another definition of NP. Complexity class NEXP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. NP-completeness: CIRC-SAT, 3-SAT.	Problem list 2
NP-completeness: NAE-3-SAT, Exactly-1-3-SAT, IND-SET, Subset-SUM, 3-COLORING.	Problem list 3
Space complexity. Classes PSPACE and NPSPACE. Configuration graph. Inclusions between time and space classes. TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) (additional material). Interpretation of PSPACE in terms of games.	Problem list 4
Probabilistic computation. Probabilistic machines, the class BPP, prime testing and Carmichael numbers, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly.	Problem list 5
Definition of Sigma_2 and Pi_2. BPP is in Sigma_2 and Pi_2. Computations with oracles, its simple properties. There are oracles A and B such that P^A is equal to NP^A and P^B is not equal to NP^B.	Problem list 6 Updated: 07.10.17
Communication protocols. Functions EQ, GT, DISJ, IP. Fooling sets. Combinatorial rectangles. Rectangle size lower bound. Rank lower bound. Non-deterministic complexity. Communication complexity classes P, NP, coNP, intersection of NP and coNP.	Problem list 7
D(f)=O(N^0(f)N^1(f)). Randomized communication complexity, definitions. R(EQ)=O(1). N^1(f) vs. R^1(f). Newman's theorem, formulation.	Problem list 8
Proof of Newman's theorem, distributional complexity and the characterization of public coin communication complexity, the discrepancy method.	Problem list 9
Randomized communication complexity of IP. Streaming algorithms. Finding the majority element. Deciding whether there is a most frequent element is hard. One-sided probabilistic complexity of disjointness.	Problem list 10 Updated: 22.11.17
Property testing: definitions, testing of halfplanes, sorted listed, connectedness of graphs, testing of linearity. Lecture notes. Version 25.11.17	Problem list 11 Updated: 22.11.17
Property testing: connectedness of graphs (cont.) and testing of monotonicity. (See notes from the previous lecture.)	Problem list 12
Property testing: lower bounds for monotonicity (see Sect 4 here) and k-linearity using communication complexity. Approximation algorithms for some NP-complete problems (see seminar).	Problem list 13
The class PCP: definition, basic properties, and relation to with the MAX-Clique approximation problem. Beginning of the proof that NP is a subset of PCP(poly(n), 1). See Dexter Kozen, "Introduction to the theory of computation", lectures 18-20 (or see the book of Arora and Barak, chapter 11).	Problem list 14
NP is a subset of PCP(poly(n),1) [continued]. Solutions of some extra problems.	No problem list.

Homework

Send homework assignments via Dropbox (the link is in the telegram group chat), or submit them in person to one of the teachers or the teaching assistant (Gleb Posobin) before the deadline.

Homework results

Results for extra problems

Office hours

	Person	Monday	Tuesday	Wednesday	Thursday	Friday
1	Vladimir Podolskii					16:40–18:00, room 621
2	Bruno Bauwens		15:05–18:00, room 620			15:05–18:00, room 620