References
[CLR] Thomas H. Cormen, Charles E. Leiserson and
Ronald L. Rivest,
Introduction to Algorithms,
The MIT Press, 1990.
[Sip] Michael
Sipser, Introduction to the Theory of Computation,
PWS Publishing Company,
1997.
[PAP] Christos
H. Papadimitriou, Computational Complexity,
[MR] Rajeev
Motwani, Prabhakar Raghavan, Randomized
Algorithms
Addison-Wesley
Publishing Company, 1995.
[V]
Vijay V. Vazirani, Approximation Algorithms. Springer.
1 |
1.03.04 Oded |
Recitation: Complexity of functions. [CLR 2-4], [Sip 7.1] Turing Machines (example – palindromes). [PAP 2.1-2.3], Multiple tape T.M. vs. Single tape ones. [PAP 2.3],[Sip 3.2] (doesn’t include time analysis). |
1 |
4.03.04 Amnon |
Time and Space complexity. [PAP 7.1] The class P. [PAP
2.6] |
2 |
8.03.04 Oded |
Multiple tape – cont. s-t-connectivity –in SPACE(log^{2}n) – an explicit machine. [PAP 7.3], [Sip 8.1] |
2 |
11.03.04 Amnon |
Composition of space bounded machines. s-t-connectivity –in SPACE(log^{2}n) – the more general framework. [PAP 7.3] Diagonalization and universal TM for Halt [PAP 3.1-2] and for complexity class separation - The Time and space hierarchies. [PAP 7.2] |
3 |
15.04.04 Oded |
Non-deterministic TM – two possible definitions. NTIME. Co-classes. [PAP 2.7,7.1] Diagonalization and universal TM for Halt and for complexity class separation. [PAP 7.2], [Sip 9.1] Circuits [PAP 11.4] |
3 |
18.03.04 Amnon |
Reductions, [PAP 8.1]
STCONN is NL-complete [PAP
7.3,16.1], CVAL is P-Complete [PAP 8.2] . |
4 |
22.03.04 Oded |
CVAL is P-Complete [PAP 8.2] |
4 |
25.03.04 Amnon |
NP. All guesses can be made at beginning. NP as a game between an all powerful prover and a polynomial time verifier. CSAT is NP-Complete. SAT, 3SAT are NP-Complete. [PAP 8.2,9.2] 2SAT is in P, in fact in co-NL. [PAP 9.2] |
5 |
29.03.04 Oded |
2-SAT is in co-NL. [PAP 9.2] 3-Col is NPC assuming 3-NAE is NPC. [PAP 9.3] |
-- |
---- |
Pessach Holiday. |
5 |
15.04.04 Amnon |
Clique, IS, VC, SetCover are NP-complete. [PAP 9.2,9.3] TQBF is PSPACE-complete. [PAP 19.1] Σ_{2}, Õ_{2}. |
6 |
19.04.04 Oded |
Self reducibility of 3-SAT: reducing the search to the decision problem by a polynomial Turing/Cook reduction. [PAP 10.3] Padding argument [PAP 20.1] applied to ex2 q6 [ans2] and to Savitch theorem. |
6 |
22.04.04 Amnon |
PH; co-NP; Oracle machines[PAP 14.3] ; Self reducibility. [PAP 10.3] PH in terms of oracles, Sigma_k=co-Pi_k , TQBF-k is Sigma_k complete. [PAP 17.2] |
-- |
26.04.04 |
Memorial day. |
7 |
29.04.04 Amnon |
NL=coNL [PAP 7.3]. Parallel computation, [PAP 15.1] . sorting in parallel. |
7 |
3.05.04 Oded |
Separating AvP from EXP Separating P from Time(2^{n}) Separating AvP from Time(2^{n}) [ans2] |
8 |
6.04.04 Amnon |
NC [PAP 15.3]. Probabilistic computation [PAP 11.1,11.2]. Chernoff. BPP amplification [PAP 11.2]. |
8 |
10.05.04 Oded |
4-NAE is NPC, 3-NAE is NPC [PAP 9.3]. PSPACE = NPSPACE revisited. Pratt's Theorem [PAP 10.2]. |
9 |
13.05.04 Amnon |
RP. Schwartz’ lemma [PAP 11.1, lemma 11.1]. Solving Perfect matching with a fast parallel, randomized algorithm[PAP 11.1]. Every BPP language is solvable by polynomial size circuits (Size(poly)) [PAP 11.4]. |
9 |
17.5.04 Oded |
Existence of 7/8 satisfying assignment for 3-CNF using probabilistic argument. s-t-Directed-Hamilton-Path is in NPC [Sip 7.35]. |
10 |
20.05.04 Amnon |
BPP is in Σ_{2} [PAP 17.2, 429-430]._{ }Approximation algorithms. Min-VC. 2-approximation of Min-VC [PAP 13.1]._{ }TSP with triangle inequality. 2-approximation of Min-TSP with triangle inequality [Vaz 3.2.1]. |
10 |
24.05.04 Oded |
2-approximation for TSP with triangle inequality [Vaz 3.2.1]. 1.5-approximation for TSP with triangle inequality |
11 |
27.05.04 Amnon |
The greedy algorithm for approximating Set-Cover [Vaz 2,2.1]. Gap problems. Promise problems. Reductions between promise problems. Hardness of gap problems implies hardness of approximation [Vaz 29.1]. Doing gap preserving reductions from MAX-3SAT to Max-Clique, MAX-IS, MIN-VC. |
11 |
31.05.04 Oded |
Hardness of gap problems implies hardness of approximation [Vaz 29.1]. Are smaller gaps harder? |
12 |
3.06.04 Amnon |
Arthur Merlin games, MA, AM, IP (All allowing Arthur to have private random coins) [Sip 10.4]. GNISO is in AM [Sip 10.4]. Quoting some theorems: several rounds collapse to AM, IP=PSPACE [Sip 10.4]. The class PCP_{s,c}(r,a) [Vaz 29.2]. |
12 |
7.06.04 Oded |
Hardness of approximation for E4-SAT and for Max-2-SAT. |
13 |
10.06.04 Amnon |
Gap_{s,c}–Max-3SAT is in PCP_{(2+s)/3,c} O((log(n)),4). Every language in PCP_{s,c=1} O((log(n)),O(1)) is reducible to Gap_{s’,c=1} Max-3SAT for some s’<1. PCP_{s<1,c=1} O((log(n)),O(log(n))) is in NP. |