Computer Science

0368.3168

Spring 2007 
Out  Due  Questions 
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 maxcut. You may allow multigraphs (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. 
Lectures

Group 1: Monday 10:0013:00,
Orenstein 103 Group 2: Thursday 09:0012:00, Dan David 001 Recitations: Tuesday 15:0016:00 Schreiber 006, 16:0017:00, 17:0018:00, 18:0019:00 Schreiber 008. 

Instructors 
Oded
Regev  Schreiber 103  6407996  Office hour: Monday 13:00 Amnon TaShma  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
Safra, Amnon
TaShma Steven Rudich from CMU Oded Goldreich from Weizmann (see also here) 

Textbooks 
Main
references:


Requirements 
Attendance, homework assignments  
Prerequisites 
Computational models, Algorithms  
Other links 
A compendium
of NPcomplete
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 
Week  Date  Class Topics 
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]; Multivssingle 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 NPcompleteness, TMSAT is NPcomplete [AB2]; The CookLeving theorem [S7.4] 
Mar 6  Multivssingle tape TM [P2.3 or S3.2].  
3  Mar 12, Mar 15  Rest of CookLevin; more NPcomplete problems: 3SAT, E3SAT, IntegerProgamming, IndependentSet, Clique, VertexCover [AB2.4]; how to deal with NPcomplete problems; Decision vs. Search [AB2.5]; what if P=NP?; More complexity classes: coNP [AB2.6] 
Mar 13  Strike  
4  Mar 19, Mar 22  EXP, NEXP; Σ_{2}^{P},
Π_{2}^{P}; the
polynomial hierarchy [AB5.1];
the time hierarchy theorem [AB3.1];
oracle machines and the limits of diagonalization (oracle A such that P^{A}
= NP^{A}) [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 P^{A}
≠ NP^{A}; Space complexity [AB4,S8]; PSPACE,
NPSPACE, L, NL; PATH in NL; Savitch's theorem [AB4.3,S8.1];
TQBF is in
PSPACE 
Mar 27  3Col is NPC [P 9.3], Composition in L [AB4 or Sip 8.1].  
6  May 28, May 31  TQBF is PSPACEcomplete; NLcompleteness [AB4.4]; NL=coNL [AB4.4.2] 
May 29  stDirected 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, SchwartzZippel [AB7] 
Jun 5 
Reciting NLhardness 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 AB1818.2] 
Jun 12  Gap problems,Hardness of GapProblems implies Hardness of approximation. [AB 18.2] Applied to 4NAE [P 9.2].  
9  Jun 18, Jun 21  Average Case Complexity [AB1515.1 P page 383] 
Jun 19 
Gap preserving properties of the reduction to Max2Sat.  
10  Jun 25 Jun 28  OWF [AB 10.1] Discrete Log and ElGamal [MOV 8.9.1]. 
Jun 26 
PCP vs. Gapproblems [AB18]. 