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²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²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] Σ₂, Õ₂.

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ⁿ)

Separating AvP from Time(2ⁿ) [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 Σ₂ [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.