ABC
1
DateTopics CoveredNotes from Ref
2
11.08.2021Turing Machine and its working, simulation of k-tapes TM by a signle-tape TM, tape Compression, halting space bounded computations, llnear speedup**[Pap94]: Chap 2; Th 2.1 (P-30); Prob 2.8.4/5/6 (P-52-53) **[AB06]: Chap 1; Claim 16 of proof (p-17); Th 1.9 (p-20) **[HU79]: Chap 7; Th 7.2 (P-161) Chap 12; Th 12.1 (P-288), 12.3 (P-290), 12.5, 12.6 , 12.7 (P-295), 12.8 (P-297), 12.9 (P-299), 12.11 (P-301), Lemma 12.1 (P-297), Ex 12.1, 12.2
3
12.08.2021Linear speedup, deterministic languages accepted by TMs in linear time, Universal TMs**[AB06]: Sec 1.4, 1.7, 1.3.1, Th 1.9, Ex 1.1
4
13.08.2021DTIME, time hierarchy, space hierarchy, DSPACE, L\subseteq NL \subseteq P \subseteq NP \subseteq PSPACE, L proper subset of PSPACE; Savitch's theorem**[HU79]: Th 12.8
5
19.08.2021Non-deterministic machines, challenge in TM programming**[Pap94]: Sec 2.7; Th 2.5, Ex 2.2
6
26.08.2021Hierarchy theorems, mergesorting on TMs
7
27.08.2021Non-deterministic timeg and space computations; Discussions on NP and NP-Ccomplete problems: HC, stable sets, graph Isomorphism, SAT, TMSAT and unsatisfiability; Reachability; Pratt's theorem; Cook-Levin theorem**[AB06]: Th 2.9
8
01.09.2021Disscussion on problems for Assignment 1; FSM, CFG; vertex cover problem
9
02.09.2021Reduction, e.g, SAT to VC
10
03.09.2021Reductions; 3SAT, VC, Clique**[Pap94]: Prop 4.3; Def 4.1
11
08.09.2021Determinism and randomization defining languages accepted in interactive protocols; Various complexity classes captured by such protocols like NP, BPP, etc.; Graph non-isomorphism interactive protocol using privte coins of Bob.
12
09.09.2021Circuit satisfiability reduces to SAT; concatenating two reductions in log space; SAT instance from CIRCUIT-SAT; NAESAT reduces to 3-coloring; NAESAT reduces to MAXCUT
13
10.09.2021Deriving a SAT instance from CIRCUIT-SAT instance; NAESAT reduces to MAXCUT, Input : G(V, E), k <= e, Question : Is there a cut of size at least k ? ; Continuation of Immerman-Szelepscenyi Theorem**[Pap94]: Th 9.3
14
15.09.2021Construction of a cut where we want to show cut of size 5m if and only if there is a NAESAT truth assignment for the formula.
15
16.09.2021Boolean circuits; Polynomial sized boolean circuits may have logarithmic or polynomial depth; Class RP; RP turns out to be subset of class NP; BPP has polynomial ckts.
16
22.09.2021Probabilistic TM; The classes BPTIME and BPP;
17
23.09.2021Aspects of parallel computing; CREW PRAM Model; NC1, NC2 Complexity classes; uniform families of circuits.
18
24.09.2021PRAMs from RAMs, Uniform family of PRAMs; register configurations; oracles for deterministic as well as for non-deterministic machines; PSPACE-Completeness for QBF, context-sensitive recognition; **[Pap94]: Prop 11.2; Th 4.3, 11.4, 11.6, 15.1, 15.2; Ex 4.2; Prob 4.4.5/8/10/12, 15.5.4
19
29.09.2021Polynomial hierarchy introduction; MINIMUM CIRCUIT Problem; SUCCINCT SET COVER Problem; Master tour property; Vapnik-Chervonenkis (VC-) dimension property; Probability amplification.**[Pap94]: Prop 9.1; Def 17.2; Prob 17.3.11 **[AB06]: Def 5.1, 5.3; Th 5.12 of Sec 5.5, Prob 5.1/3/10/12 **[MR00]: Th 4.2
20
30.09.2021Polynomial hierarchy (PH), definition of PH via oracle machines, Balanced relationships-certificates definition of PH, Karp-Lipton Theorem, Meyer's Theorem, Class P/poly, BPP**[Pap94]: Th 17.2, 17.8; Prop 9.1; Corollary 1 **[AB06]: Def 5.3, 6.5; Th 5.12, 6.19, 6.20
21
01.10.2021Membership of BPP in Sigma 2, Ī£iSAT(Sigma_i SAT) problem, characterization of languages in Sigma _i, Derandomizing BPP into Sigma_2, probability amplification, SUCCINCT SET COVER problem, MINIMUM CIRCUIT problem, Vapnik- Chervonenkis (VC-) dimension problem
22
06.10.2021PSPACE and EXPCOM oracles **[Pap94]: Th 17.8, Th 17.9; Corollary 2
23
07.10.2021Derandomizing BPP by reducing the number of random bits, Alternating Turing Machines
24
08.10.2021Unless the polynomial hierarchy collapses, PH != PSPACE (Assume PH=PSPACE: Prove TQBF to be PH-Complete, to show collapse of polynomial heirarchy)**Claim 5.5 in [AB06]
25
20.10.2021Barak: Th 5.12 pg 102
26
21.10.2021QSAT is a complete problem for PSPACE, using ideas from the proof of Savitch's theorem and quantifying states to keep inductively constructed QSAT formula polynomial in size.
27
27.10.2021Test 2: Q1- NL completeness of directed and strongly connected graph. Q5- NC1 is subset of L. Logspace algorithms are also being used to construct the uniform families of circuits.
28
28.10.2021Karp-Lipton Theorem, Meyer's Theorem, Polynomial Advice
29
29.10.21Oblivious UTMs, Sketch of Karp-Lipton and Meyer's theorems, polynomial advise, P/poly, sparse languages.
30
03.11.21Stochastic satisfiabiiity (SSAT), Probabilistic TMs, AP, APP, PSPACE. IP=PSPACE discussion and proof.Prop. 19.1 [Pap94], Theorem 19.5, Theorem 19.6
31
05.11.21IP=PSPACE proof protocol for QSAT (contd.), seminar by Rahul on non-deterministic time and space hierarchy theorems, seminar by Debojyoti on Ladner's theorem's proof.
32
10.11.21Seminars by Arnab on Karp-Lipton theorem and Meyer's theorem, and by Amatya on the separating oracle for P and NP.
33
11.11.21Amatya continued his presentation and Rahul explained MINLA NP-Completeness proof
34
12.11.21Presentation by Manideep on elements of quantum circuits and the relationship of BQP with PSPACE, P and BPP.