Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Derandomization**- 5 meetings- Meeting 01 : Wed, Apr 20, 08:00 am-08:50 am
- Meeting 02 : Fri, Apr 22, 12:00 pm-12:50 pm
- Meeting 03 : Mon, Apr 25, 10:00 am-10:50 am
- Meeting 04 : Tue, Apr 26, 09:00 am-09:50 am
- Meeting 05 : Wed, Apr 27, 08:00 am-08:50 am

The BPP vs P problem. Pseudorandom generators. Nisan-Wigderson construction of PRGs (overview). References [MB Notes] Exercises Reading The BPP vs P problem. Pseudorandom generators. Nisan-Wigderson construction of PRGs (overview).References: [MB Notes] Proof of N-W constructions: Hybrid argument. References [MBNotes] Exercises Reading Proof of N-W constructions: Hybrid argument.References: [MBNotes] To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None To Be Announced References Exercises Reading To Be AnnouncedReferences: None **Theme 2 : Complexity of Counting**- 7 meetings- Meeting 06 : Mon, Jan 11, 10:00 am-10:50 am
- Meeting 07 : Tue, Jan 12, 09:00 am-09:50 am
- Meeting 08 : Wed, Jan 13, 08:00 am-08:50 am
- Meeting 09 : Fri, Jan 15, 12:00 pm-12:50 pm
- Meeting 10 : Mon, Jan 18, 10:00 am-10:50 am
- Meeting 11 : Tue, Jan 19, 09:00 am-09:50 am
- Meeting 12 : Wed, Jan 20, 08:00 am-08:50 am

Administrative announcements. Complexity of coutning. Toda's theorem. References Exercises Reading Administrative announcements. Complexity of coutning. Toda's theorem.References: None Isolating satisfying assignments: Valiant Vazirani Theorem. Proof. Isolating matchings: Mulmuley-Vazirani-Vazirani theorem (without proof). References [MB Notes 1] Exercises Reading Read Chapter 16 in [MB Notes 1] Isolating satisfying assignments: Valiant Vazirani Theorem. Proof. Isolating matchings: Mulmuley-Vazirani-Vazirani theorem (without proof).References: [MB Notes 1] Reading: Read Chapter 16 in [MB Notes 1] Valiant Vazirani Theorem. References Exercises Reading Valiant Vazirani Theorem.References: None Proof of Valiant - Vazirani (contd). The class Parity-P. References Exercises Reading Proof of Valiant - Vazirani (contd). The class Parity-P.References: None Properties of parity-P: Closure under complementation, and Turing reductions. References Exercises Reading Properties of parity-P: Closure under complementation, and Turing reductions.References: None BP-operator. Probability amplification. BP operator with quantifiers. References Exercises Reading BP-operator. Probability amplification. BP operator with quantifiers.References: None Proof of Toda's theorem. References Exercises Reading Proof of Toda's theorem.References: None **Theme 3 : Proof Systems**- 25 meetings- Meeting 13 : Fri, Jan 22, 12:00 pm-12:50 pm
- Meeting 14 : Mon, Jan 25, 10:00 am-10:50 am
- Meeting 15 : Tue, Jan 26, 09:00 am-09:50 am
- Meeting 16 : Wed, Jan 27, 08:00 am-08:50 am
- Meeting 17 : Fri, Jan 29, 12:00 pm-12:50 pm
- Meeting 18 : Tue, Feb 02, 09:00 am-09:50 am
- Meeting 19 : Wed, Feb 03, 08:00 am-08:50 am
- Meeting 20 : Fri, Feb 05, 12:00 pm-12:50 pm
- Meeting 21 : Mon, Feb 08, 10:00 am-10:50 am
- Meeting 22 : Tue, Feb 09, 09:00 am-09:50 am
- Meeting 23 : Wed, Feb 10, 08:00 am-08:50 am
- Meeting 24 : Fri, Feb 12, 12:00 pm-12:50 pm
- Meeting 25 : Mon, Feb 15, 10:00 am-10:50 am
- Meeting 26 : Tue, Feb 16, 09:00 am-09:50 am
- Meeting 27 : Wed, Feb 17, 08:00 am-08:50 am
- Meeting 28 : Fri, Feb 19, 12:00 pm-12:50 pm
- Meeting 29 : Mon, Feb 22, 10:00 am-10:50 am
- Meeting 30 : Tue, Feb 23, 09:00 am-09:50 am
- Meeting 31 : Wed, Feb 24, 08:00 am-08:50 am
- Meeting 32 : Thu, Feb 25, 04:00 pm-05:45 pm
- Meeting 33 : Fri, Feb 26, 12:00 pm-12:50 pm
- Meeting 34 : Mon, Feb 29, 10:00 am-10:50 am
- Meeting 35 : Tue, Mar 01, 09:00 am-09:50 am
- Meeting 36 : Wed, Mar 02, 08:00 am-08:50 am
- Meeting 37 : Fri, Mar 04, 12:00 pm-12:50 pm

Proof of isolation lemma. Introduction to proof systems. NP as a prover-verifier system. Generalization to a probabilistic verifier. Definition of interactive proof systems. The class IP. References [MB Notes 1] Exercises Reading Read the <a href="https://www.cs.princeton.edu/courses/archive/spring07/cos522/BabaiEmail.pdf"> article </a> by Babai for an account of development of interactive proof systems. Proof of isolation lemma. Introduction to proof systems. NP as a prover-verifier system. Generalization to a probabilistic verifier. Definition of interactive proof systems. The class IP.References: [MB Notes 1] Reading: Read the article by Babai for an account of development of interactive proof systems. No class (due to Shastra) References Exercises Reading No class (due to Shastra)References: None No lecture (republic day) References Exercises Reading No lecture (republic day)References: None No Lecture (instructor out of town) References Exercises Reading No Lecture (instructor out of town)References: None No Lecture. References Exercises Reading No Lecture.References: None Definition of interactive proof systems. A protocol for graph non-isomorphism. References [MB Notes 1] Exercises Reading Definition of interactive proof systems. A protocol for graph non-isomorphism.References: [MB Notes 1] IP is contained in PSPACE. References The proof is from [Kozen2] chapter 17. Also see [MBnotes]. Exercises Reading IP is contained in PSPACE.References: The proof is from [Kozen2] chapter 17. Also see [MBnotes]. Shamir's theorem: IP=PSPACE. Arithemtization of QBF. References [MBnotes1]. Also see [Kozen2] Exercises Reading Shamir's theorem: IP=PSPACE. Arithemtization of QBF.References: [MBnotes1]. Also see [Kozen2] Shamir's theorem (contd) References Exercises Reading Shamir's theorem (contd)References: None Public coin protocols: Arthur vs Merlin. The class AM. GraphNonIso is in AM: a public coin protocol for graph non-isomorphism. References [MBNotes1] and [AB] Exercises Reading Public coin protocols: Arthur vs Merlin. The class AM. GraphNonIso is in AM: a public coin protocol for graph non-isomorphism.References: [MBNotes1] and [AB] Public coin protocol for Graph non isomorphism (contd). Public vs private coin (without proof). GI is NP complete implies PH collapses. References [AB] For the proofs of public vs private coin proof systems, and constant round vs two round AM, see <a href="http://courses.cs.washington.edu/courses/cse532/04sp/"> lecture notes</a> (Lectures 9 and 10) by Paul Beame. Exercises Reading Public coin protocol for Graph non isomorphism (contd). Public vs private coin (without proof). GI is NP complete implies PH collapses.References: [AB] For the proofs of public vs private coin proof systems, and constant round vs two round AM, see lecture notes (Lectures 9 and 10) by Paul Beame. GI is not NP complete unless PH collapses (contd). More on proof systems. Zero knowledge. Probabilistically checkable proofs. References [AB] for GI. [MBNotes2] for PCP. Exercises Reading See<a href="http://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf"> History of PCP </a> a chronological note on the developments that lead to the PCP theorem. GI is not NP complete unless PH collapses (contd). More on proof systems. Zero knowledge. Probabilistically checkable proofs.References: [AB] for GI. [MBNotes2] for PCP. Reading: See History of PCP a chronological note on the developments that lead to the PCP theorem. Probablistically checkable Proofs. Definition. Relation to hardness of approximation. References Exercises Reading Probablistically checkable Proofs. Definition. Relation to hardness of approximation.References: None PCPs and hardness of approximation(contd) References Exercises Reading PCPs and hardness of approximation(contd)References: None Approximation algorithm and Gap problems. Weak PCP theorem. PCP for LIN. References [MBNotes2] and <a href="http://www.cse.cuhk.edu.hk/~andrejb/csci5170/s10/notes/10L12.pdf"> Lecture notes </a> by Andrej Bogdanov Exercises Reading Approximation algorithm and Gap problems. Weak PCP theorem. PCP for LIN.

Scribe : Vijayaraghunathan (notes being written up)Scribe : Key : References: [MBNotes2] and Lecture notes by Andrej Bogdanov PCP for LIN. Failed attempts. Need for linearity test. Notion of distance for Boolean functions. References [MBnotes 2] and Notes by Bogdanov. Exercises Reading PCP for LIN. Failed attempts. Need for linearity test. Notion of distance for Boolean functions.

Scribe : A Sundar. (rough draft; better one coming soon)Scribe : Key : References: [MBnotes 2] and Notes by Bogdanov. Fourier coefficients of Boolean functions. BLR Linearity test. Proof of correctness. References Exercises Reading Fourier coefficients of Boolean functions. BLR Linearity test. Proof of correctness.

Scribe : A Sundar. (notes being written up)Scribe : Key : References: None Completing PCP for LIN. Proof of Weak PCP theorem. References <a href="http://www.cse.cuhk.edu.hk/~andrejb/csci5170/s10/notes/10L12.pdf"> Notes </a> by Bogdanov. Exercises Reading Completing PCP for LIN. Proof of Weak PCP theorem.

Scribe : Santhoshini (notes being written up)Scribe : Key : References: Notes by Bogdanov. Weak PCP theorem (contd). Dinur's proof of PCP theorem. Introduction and overview. References Exercises Reading Weak PCP theorem (contd). Dinur's proof of PCP theorem. Introduction and overview.

Scribe : Santhoshini (notes being written up)Scribe : Key : References: None Dinur's proof of PCP theorem Overview (again). Step 1: Query reduction. Expander graphs. Definition os edge and spectral expansion. Relation between two. Rayleigh quotient characterization of spectral expansion. References Bogdanov's notes and [MBNotes2]. For portion on expander graphs see <a href="http://www.tcs.tifr.res.in/~prahladh/teaching/07autumn/lectures/lec678.pdf"> Lecture notes </a> by Prahladh Harsha Exercises Reading Dinur's proof of PCP theorem Overview (again). Step 1: Query reduction. Expander graphs. Definition os edge and spectral expansion. Relation between two. Rayleigh quotient characterization of spectral expansion.

Scribe : Subhadra (notes being written up)Scribe : Key : References: Bogdanov's notes and [MBNotes2]. For portion on expander graphs see Lecture notes by Prahladh Harsha Relation between spectral and edge expansion (proof of one direction). References See <a href="http://www.tcs.tifr.res.in/~prahladh/teaching/07autumn/lectures/lec678.pdf"> Lecture notes </a> by Prahladh Harsha. Exercises Reading Relation between spectral and edge expansion (proof of one direction).

Scribe : Shijin (notes being written up)Scribe : Key : References: See Lecture notes by Prahladh Harsha. Randomk walks on expanders. Expander mixing. Step 2 in Dinur's proof: Degree reduction. References See Lecture notes by Prahladh Harsha. Exercises Reading Randomk walks on expanders. Expander mixing. Step 2 in Dinur's proof: Degree reduction.

Scribe : Shijin (notes being written up)Scribe : Key : References: See Lecture notes by Prahladh Harsha. Expanderization. Random walk in the expanderized constraint graph. References Exercises Reading Expanderization. Random walk in the expanderized constraint graph.

Scribe : Shiva Krishna (notes being written up)Scribe : Key : References: None Gap amplification: Overview. The verifier GP-VER. References See <a href="http://www.tcs.tifr.res.in/~prahladh/teaching/07autumn/lectures/lec678.pdf"> Lecture notes </a> by Prahladh Harsha. Exercises Reading Gap amplification: Overview. The verifier GP-VER.

Scribe : Shiva Krishna (notes being written up)Scribe : Key : References: See Lecture notes by Prahladh Harsha. Gap Amplification: analysis of the ther verifier GP-VER with Lazy random walks References Exercises Reading Gap Amplification: analysis of the ther verifier GP-VER with Lazy random walks

Scribe : Kavin Kumar (notes being written up)Scribe : Key : References: None **Theme 4 : Circuit Complexity**- 25 meetings- Meeting 38 : Tue, Mar 08, 09:00 am-09:50 am
- Meeting 39 : Fri, Mar 11, 12:00 pm-12:50 pm
- Meeting 40 : Mon, Mar 14, 10:00 am-10:50 am
- Meeting 41 : Tue, Mar 15, 09:00 am-09:50 am
- Meeting 42 : Wed, Mar 16, 08:00 am-08:50 am
- Meeting 43 : Fri, Mar 18, 12:00 pm-12:50 pm
- Meeting 44 : Mon, Mar 21, 10:00 am-10:50 am
- Meeting 45 : Tue, Mar 22, 09:00 am-09:50 am
- Meeting 46 : Wed, Mar 23, 08:00 am-08:50 am
- Meeting 47 : Mon, Mar 28, 10:00 am-10:50 am
- Meeting 48 : Tue, Mar 29, 09:00 am-09:50 am
- Meeting 49 : Wed, Mar 30, 08:00 am-08:50 am
- Meeting 50 : Fri, Apr 01, 12:00 pm-12:50 pm
- Meeting 51 : Mon, Apr 04, 10:00 am-10:50 am
- Meeting 52 : Tue, Apr 05, 09:00 am-09:50 am
- Meeting 53 : Wed, Apr 06, 08:00 am-08:50 am
- Meeting 54 : Thu, Apr 07, 11:00 am-12:00 pm
- Meeting 55 : Fri, Apr 08, 10:00 am-11:00 am
- Meeting 56 : Mon, Apr 11, 10:00 am-10:50 am
- Meeting 57 : Tue, Apr 12, 09:00 am-09:50 am
- Meeting 58 : Tue, Apr 12, 12:00 pm-01:00 pm
- Meeting 59 : Wed, Apr 13, 08:00 am-08:50 am
- Meeting 60 : Mon, Apr 18, 10:00 am-10:50 am
- Meeting 61 : Tue, Apr 19, 09:00 am-09:50 am
- Meeting 62 : Thu, Apr 21, 04:00 pm-06:00 pm

Lecture Cancelled. References Exercises Reading Lecture Cancelled.References: None Alphabet reduction (Sketch of the proof). Introduction to Boolean Circuits. References For Boolean circuits, see <a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture34.pdf"> Notes </a> from an earlier offering of the course. Exercises Reading Alphabet reduction (Sketch of the proof). Introduction to Boolean Circuits.References: For Boolean circuits, see Notes from an earlier offering of the course. Post's characterization of complete basis. Complexity measures for Boolean Circuits: Size, Depth, Width. References <a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture34.pdf"> Notes </a> from an earlier offering of the course. Exercises Reading Post's characterization of complete basis. Complexity measures for Boolean Circuits: Size, Depth, Width.References: Notes from an earlier offering of the course. Shannon's Lower boound. Lupanov's upper bound. References <a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture35.pdf"> Notes </a> from an earlier offering of the course. Exercises Reading Shannon's Lower boound. Lupanov's upper bound.References: Notes from an earlier offering of the course. Lupanov's upper bound (contnued). Definitiong of PSIZE. Non uniform complexity classes. P/poly = PSIZE. Karp Lipton theorem. References <a href="http://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture36.pdf"> Notes</a> from an earlier offering of the course. Exercises Reading Lupanov's upper bound (contnued). Definitiong of PSIZE. Non uniform complexity classes. P/poly = PSIZE. Karp Lipton theorem.References: Notes from an earlier offering of the course. Karp-Lipton theorem: NP subseteq P/poly implies PH collapses. Proof. References [MBNotes] Exercises Reading Karp-Lipton theorem: NP subseteq P/poly implies PH collapses. Proof.References: [MBNotes] Notion of uniformity for circuits: P-uniform and los-space uniform circuits. Uniform circuit complexity classes. Circuit complexity classes: NCi. NC hierarchy. Sequentiol vs Parallel computation. Parity is in NC1. Reach is in NC2. References [Vollmer] Exercises Reading Notion of uniformity for circuits: P-uniform and los-space uniform circuits. Uniform circuit complexity classes. Circuit complexity classes: NCi. NC hierarchy. Sequentiol vs Parallel computation. Parity is in NC1. Reach is in NC2.References: [Vollmer] The NC Hierarchy. ADD is in NC1. Definition of AC. ADD is in AC0. Reach is in AC1. AC0 vs NC1. References See [Vollmer] for a more detailed exposition. Exercises Reading The NC Hierarchy. ADD is in NC1. Definition of AC. ADD is in AC0. Reach is in AC1. AC0 vs NC1.References: See [Vollmer] for a more detailed exposition. More functions inside NC1: ITerated-Addition (ITADD), Bit Count (BCOUNT), Majority (MAJ) and Threshold functions. Comparing functions inside NC1: constant depth reductions. Comparing functions MULT, ITADD, BCOUNT and MAJ. References See [Vollmer] for a more detailed exposition. Exercises Reading More functions inside NC1: ITerated-Addition (ITADD), Bit Count (BCOUNT), Majority (MAJ) and Threshold functions. Comparing functions inside NC1: constant depth reductions. Comparing functions MULT, ITADD, BCOUNT and MAJ.References: See [Vollmer] for a more detailed exposition. ITADD constand depth reduces to BCOUNT. ITADD, BCOUNT, MAJ, Th and MULT are constant depth equivalent. logITADD is in AC0. References [Vollmer] Exercises Reading ITADD constand depth reduces to BCOUNT. ITADD, BCOUNT, MAJ, Th and MULT are constant depth equivalent. logITADD is in AC0.References: [Vollmer] Threshold circuits. The TC hierarchy: TC^i. Symmetric functions. Parity vs AC0. Definition of the class ACC0. Formula vs NC1 References Your class notes. Also see [vollmer] Exercises Reading Threshold circuits. The TC hierarchy: TC^i. Symmetric functions. Parity vs AC0. Definition of the class ACC0. Formula vs NC1References: Your class notes. Also see [vollmer] Formula = NC1. Branching programs. References Your class notes. Exercises Reading Formula = NC1. Branching programs.References: Your class notes. Barrington's theorem: NC1= BWBP. Proof. References <a href="http://www.complexity.ethz.ch/education/Lectures/ComplexityHS10/ScriptChapterTwelve"> See</a> T. Holenstein's lecture notes. Also see, <a href="http://www.ccs.neu.edu/home/viola/classes/gems-08/lectures/le11.pdf"> Notes </a> by E. Viola. Exercises Reading Barrington's theorem: NC1= BWBP. Proof.Barrington's Theorem (contd). References Exercises Reading Barrington's Theorem (contd).References: None Circuit lower bounds. Gate elimination method. References [vollmer] Exercises Reading Circuit lower bounds. Gate elimination method.References: [vollmer] Gate elimination method 2: lower bound for parity. Nechiporuk's formula size lower bound. References Your class notes. Exercises Reading Gate elimination method 2: lower bound for parity. Nechiporuk's formula size lower bound.References: Your class notes. Nechiporuk's formula size lower bound. References [Jukna] Exercises Reading Nechiporuk's formula size lower bound.References: [Jukna] Effect of restrictions. Random restrictions on formulas: Subbatovskaya's theorem. References [Jukna] Exercises Reading Effect of restrictions. Random restrictions on formulas: Subbatovskaya's theorem.References: [Jukna] Andreev's cubic lower bound. Lower bounds against constant depth circuits. Hastad's switching lemma. References [Jukna] Exercises Reading Andreev's cubic lower bound. Lower bounds against constant depth circuits. Hastad's switching lemma.References: [Jukna] Proof of the switching lemma. References [Jukna] Exercises Reading Proof of the switching lemma.References: [Jukna] Parity not in AC0. References [Jukna] Exercises Reading Parity not in AC0.References: [Jukna] Polynomial method. Approximation of AC0 by polynomials. References [MBNotes] Exercises Reading Polynomial method. Approximation of AC0 by polynomials.References: [MBNotes] Parity cannot be approximated by low degree polynomials. References [MBNotes] Exercises Reading Parity cannot be approximated by low degree polynomials.References: [MBNotes] Lower bound for parity via polynomial method (contd) References Exercises Reading Lower bound for parity via polynomial method (contd)References: None TBA References Exercises Reading TBAReferences: None **Theme 5 : Evaluation Meetings**- 3 meetings- Meeting 63 : Sat, Mar 12, 02:00 pm-03:30 pm
- Meeting 64 : Sat, Apr 23, 01:00 pm-01:50 pm
- Meeting 65 : Sat, Apr 23, 01:55 pm-02:45 pm

Syllabus: Complexity of counting + Proof systems. References Exercises Reading Syllabus: Complexity of counting + Proof systems.References: None Matching is in Quasi NC. (Sundar A) References http://eccc.hpi-web.de/report/2015/177/download/ Exercises Reading Matching is in Quasi NC. (Sundar A)References: http://eccc.hpi-web.de/report/2015/177/download/ TBA References Exercises Reading TBAReferences: None