|Jun 21||End of Term||1. Prove that PCP1/2,1[lg n, lg n] is in NP.
2. Solve Q15 from [AB 2.7] regarding max-cut.
You may allow multi-graphs (i.e, parallel edges are allowed).
Hint: start from 3NAE,with a triangle for evey clause, and parallel edges between a vartex of a variable and its negation.
|Jun 12||Jun 26||Problem set 3: 3
Problem set 5: 5,6
Problem set 6: 3, 4a
Problem set 8: 2
|May 29||12 Jun||Problem set 3: 1,2
Problem set 4: 4,6
Problem set 5: 4
|Mar 20||Apr 10||Problem set 5: 2
Problem set 10: 1, and 3 (prove SAT<p HALT instead of SAT <L HALT)
Problem set 8: 1 (without assuming 11:1).
Problem set 11: 1
|Mar 6||Mar 20||Show that if L can be decided by a machine M then L can also be decided by a machine M' with working alphabet set of size at most 4, such that the running time of M' is at most c times the running time of M (where c is a constant, which may depend on M).|
|Feb 28||Mar 13||Problem set 1: 1a, 1b except the first and the last, 2. Problem set 2: 4, 5.|
|| Group 1: Monday 10:00-13:00,
Group 2: Thursday 09:00-12:00, Dan David 001
Recitations: Tuesday 15:00-16:00 Schreiber 006,
16:00-17:00, 17:00-18:00, 18:00-19:00 Schreiber 008.
Regev | Schreiber 103 | 6407996 | Office hour: Monday 13:00
Amnon Ta-Shma | Schreiber 127 | 6405364
T.A.: Oded Schwartz | Schreiber Open Space | 6405398 | Office hour: Tuesday 19:10
|Lecture notes on the web||Previous courses in TAU by Muli
Steven Rudich from CMU
Oded Goldreich from Weizmann (see also here)
||Attendance, homework assignments|
||Computational models, Algorithms|
problems and what's known about them.
A compendium of problems in higher levels of the hierarchy, part I and part II.
The zoo of all(?) known complexity classes.
Previous exams in our course
|1||Feb 26, Mar 1||Administration; Historical remarks; Computability [AB1, S part II]: languages, the Turing machine model of computation and its robustness, the universal turing machine, uncomputable functions; Time complexity [AB2,S7]: the class P|
|Feb 27||Administration; Reciting O notations [AB1 or CLR]; Multi-vs-single tape TM - to be continued [P2.3 or S3.2].|
|2||Mar 5, Mar 8||The class NP, problems in NP, alternative definitions of NP, reductions and NP-completeness, TMSAT is NP-complete [AB2]; The Cook-Leving theorem [S7.4]|
|Mar 6||Multi-vs-single tape TM [P2.3 or S3.2].|
|3||Mar 12, Mar 15||Rest of Cook-Levin; more NP-complete problems: 3SAT, E3SAT, IntegerProgamming, IndependentSet, Clique, VertexCover [AB2.4]; how to deal with NP-complete problems; Decision vs. Search [AB2.5]; what if P=NP?; More complexity classes: coNP [AB2.6]|
|4||Mar 19, Mar 22||EXP, NEXP; Σ2P,
polynomial hierarchy [AB5.1];
the time hierarchy theorem [AB3.1];
oracle machines and the limits of diagonalization (oracle A such that PA
= NPA) [AB3.5]
|Mar 20||4NAE and 3NAE are NPC [PAP 9.2]. 3Col is NPC [PAP 9.3] (to be continued).|
|5||Mar 26, May 24||Oracle A such that PA
≠ NPA; Space complexity [AB4,S8]; PSPACE,
NPSPACE, L, NL; PATH in NL; Savitch's theorem [AB4.3,S8.1];
TQBF is in
|Mar 27||3Col is NPC [P 9.3], Composition in L [AB4 or Sip 8.1].|
|6||May 28, May 31||TQBF is PSPACE-complete; NL-completeness [AB4.4]; NL=coNL [AB4.4.2]
|May 29||st-Directed Hamilton Path is NPC [AB2.4 or Sip 7.35].|
|7||Jun 4, Jun 7||What we did so far and what are we going to do next.
Randomized computation; checking AB=C, Schwartz-Zippel [AB7]
||Reciting NL-hardness and Immerman Theorem|
|Jun 8 A||Chernoff [AB 7.4] , RP [AB 7.3 PAP 11].|
|Jun 8 B||Approximation Algorithms: Vertex Cover [P 13.1], Set Cover [V2,2.1].|
|8||Jun 11, Jun 14||Approximation algorithms, The PCP Theorem, Hardness of approximation [V2 AB18-18.2]|
|Jun 12||Gap problems,Hardness of Gap-Problems implies Hardness of approximation. [AB 18.2] Applied to 4NAE [P 9.2].|
|9||Jun 18, Jun 21||Average Case Complexity [AB15-15.1 P page 383]|
||Gap preserving properties of the reduction to Max2Sat.|
|10||Jun 25 Jun 28||OWF [AB 10.1] Discrete Log and El-Gamal [MOV 8.9.1].|
||PCP vs. Gap-problems [AB18].|