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 : Probability Toolkit**- 6 meetings- Meeting 01 : Wed, Jan 14, 02:00 pm-04:00 pm - Rajsekar Manokaran
- Meeting 02 : Fri, Jan 16, 02:00 pm-04:00 pm - Rajsekar Manokaran
- Meeting 03 : Wed, Jan 21, 02:00 pm-04:00 pm - Rajsekar Manokaran
- Meeting 04 : Fri, Jan 23, 02:00 pm-04:00 pm - Rajsekar Manokaran
- Meeting 05 : Wed, Jan 28, 02:00 pm-04:00 pm - Rajsekar Manokaran
- Book on the Discrepancy Method by Chazelle; Chapter 1
- Meeting 06 : Fri, Jan 30, 02:00 pm-04:00 pm - Rajsekar Manokaran

Introduction to Probabilistic Method; basic notions in probability; random variables; expectation, variance and standard deviation; Markov inequality; Chebyshev inequality; Chernoff inequality. References Exercises Reading Introduction to Probabilistic Method; basic notions in probability; random variables; expectation, variance and standard deviation; Markov inequality; Chebyshev inequality; Chernoff inequality.References: None Conditional probability spaces; Martingales; Azuma-Hoeffding inequalities. References Exercises Reading Conditional probability spaces; Martingales; Azuma-Hoeffding inequalities.References: None Application of Martingales: analysing coin tossing protocols. References Exercises Reading Application of Martingales: analysing coin tossing protocols.References: None Doob's Martingale process; Erdos-Renyi model for generating random graphs; Probabilistic bounds on the chromatic number of random graphs References <ul><li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1797">Paper on Coin-Tossing and Martingales</a></li></ul> Exercises Reading Doob's Martingale process; Erdos-Renyi model for generating random graphs; Probabilistic bounds on the chromatic number of random graphsReferences: Entropy Method; Spencer's bound on the discrepancy of set systems References <ul> <li><a href="https://www.cs.princeton.edu/~chazelle/pubs/book.pdf">Book on the Discrepancy Method by Chazelle</a>; Chapter 1</a></li> </ul> Exercises Reading Entropy Method; Spencer's bound on the discrepancy of set systemsReferences: Lovasz local lemma; Application to routing protocols References <ul><li><a href="http://www.cs.berkeley.edu/~sinclair/cs271/n22.pdf">Alistair Sinclair's lecture notes</a>;</li> <li> <a href="http://www.cs.duke.edu/~bmm/data/pubs/LeightonMR94.pdf">Original paper on routing protocols</a></li> Exercises Reading Lovasz local lemma; Application to routing protocols**Theme 2 : Algorithmic Coding Theory**- 9 meetings- Meeting 07 : Wed, Feb 04, 02:00 pm-04:00 pm - Jayalal Sarma
- Meeting 08 : Fri, Feb 06, 03:00 pm-05:00 pm - Jayalal Sarma
- Meeting 09 : Wed, Feb 11, 02:00 pm-04:00 pm - Jayalal Sarma
- Meeting 10 : Fri, Feb 13, 03:00 pm-05:00 pm - Jayalal Sarma
- Meeting 11 : Wed, Feb 18, 02:00 pm-04:00 pm - Jayalal Sarma
- Meeting 12 : Fri, Feb 20, 03:00 pm-05:00 pm - Jayalal Sarma
- Meeting 13 : Wed, Feb 25, 02:00 pm-04:00 pm - Jayalal Sarma
- Meeting 14 : Fri, Feb 27, 02:00 pm-04:00 pm - Jayalal Sarma
- Meeting 15 : Mon, Mar 02, 03:00 pm-05:00 pm - Jayalal Sarma

Shannon's view. Modeling the channel. Shannon's Source Coding Theorem. Shannon's Noisy Coding Theorem. References Lecture notes sent out. Till then, <a href="http://people.csail.mit.edu/madhu/FT01/scribe/lect1.ps">this is a good reference</a>. Exercises Reading <ul> <li><a href="www.cs.cmu.edu/~venkatg/teaching/ITCS-spr2013/notes/15359-2009-lecture25.pdf">Venkat Guruswami's Notes on Entropy</a></li> </ul> Shannon's view. Modeling the channel. Shannon's Source Coding Theorem. Shannon's Noisy Coding Theorem.References: Lecture notes sent out. Till then, this is a good reference. Reading: A combinatorial and constructive view : minimum distance and rate. A simple application of codes : Constructing hash families from codes. Basic code constructions. Hamming code. Generating Matrix and Parity Check Matrix. Can better rate be achieved for d=3? The Hamming Bound. Characterization of minimum distance. Generalized Hamming Codes. Distance. Parity Check matrix vs Generator Matrix. References Lecture Notes. Exercises Reading A combinatorial and constructive view : minimum distance and rate. A simple application of codes : Constructing hash families from codes. Basic code constructions. Hamming code. Generating Matrix and Parity Check Matrix. Can better rate be achieved for d=3? The Hamming Bound. Characterization of minimum distance. Generalized Hamming Codes. Distance. Parity Check matrix vs Generator Matrix.References: Lecture Notes. Dual of a Code. Hadamard Code. Distance of Hadamard Code. Singleton Bound. Reed-Solomon Codes. Reed-Muller Codes, Concatenation Codes - Bounds and parameters. Schwartz-Zippel Lemma. References Lecture Notes. Exercises Reading Dual of a Code. Hadamard Code. Distance of Hadamard Code. Singleton Bound. Reed-Solomon Codes. Reed-Muller Codes, Concatenation Codes - Bounds and parameters. Schwartz-Zippel Lemma.References: Lecture Notes. Unique decoding problem. Trivial algorithms Decoding problem for Reed-Solomon Codes. Error locating Polynomials. Berlekamp-Welsh decoding algorithm for Reed-Solomon Codes. References Lecture Notes sent out Exercises Reading Unique decoding problem. Trivial algorithms Decoding problem for Reed-Solomon Codes. Error locating Polynomials. Berlekamp-Welsh decoding algorithm for Reed-Solomon Codes.References: Lecture Notes sent out List decoding problem. Johnson's bound. List decoding of Reed-Solomon Codes. A bivariate view of the Berlekamp-Welsh decoding algorithm. Sudan's list decoding algorithm. A References GRS Textbook Exercises Reading Amplification of number of roots by the method of multiplicities. Guruswami-Sudan List Decoding Algorithm for Reed-Solomon codes that achieves the Johnson's bound. List decoding problem. Johnson's bound. List decoding of Reed-Solomon Codes. A bivariate view of the Berlekamp-Welsh decoding algorithm. Sudan's list decoding algorithm. AReferences: GRS Textbook Reading: Amplification of number of roots by the method of multiplicities. Guruswami-Sudan List Decoding Algorithm for Reed-Solomon codes that achieves the Johnson's bound. Application : An efficient algorithm computing Permanent for 1/2+epsilon fraction of input will imply an efficient randomized algorithm for permanent that works for all inputs.<br> Outline of Cai-Pavan-Sivakumar algorithm. References Refer to class lecture notes. Exercises Reading Application : An efficient algorithm computing Permanent for 1/2+epsilon fraction of input will imply an efficient randomized algorithm for permanent that works for all inputs.

Outline of Cai-Pavan-Sivakumar algorithm.References: Refer to class lecture notes. Cai-Pavan-Sivakumar - Efficiently computing permanent in atleast 1/n^k fraction of inputs will imply an efficient randomized algorithm for permanent that works for all inputs. Tool : Sudan's list-decoding algorithm. References <a href="http://pages.cs.wisc.edu/~jyc/papers/permanent.ps">Original Paper</a> Exercises Reading Cai-Pavan-Sivakumar - Efficiently computing permanent in atleast 1/n^k fraction of inputs will imply an efficient randomized algorithm for permanent that works for all inputs. Tool : Sudan's list-decoding algorithm.References: Original Paper Sublinear Time Decoding : Locally decodable codes. Applications to Private information Retrieval. Local Smooth Decoder, that suits both purposes. Local Smooth decoder for Hadamard code. Rate vs Query Complexity. References <a href="http://arxiv.org/abs/cs/0409044">Luca Trevisan's Survey</a> (section 3) Exercises Reading Sublinear Time Decoding : Locally decodable codes. Applications to Private information Retrieval. Local Smooth Decoder, that suits both purposes. Local Smooth decoder for Hadamard code. Rate vs Query Complexity.References: Luca Trevisan's Survey (section 3) Two systematic variants of Reed-Muller Codes. Variant 1 : High rate, high query complexity perfect smooth decoder version.<br> Variant 2 : Low rate, constant query complexity perfect smooth decoder.<br> Locally decodable codes for hardness amplification within E. Conversion from worst-case hard Boolean function to average-case hard Boolean function using a local decoder. References <a href="http://arxiv.org/abs/cs/0409044">Luca Trevisan's Survey</a> (section 3) Exercises Reading Two systematic variants of Reed-Muller Codes. Variant 1 : High rate, high query complexity perfect smooth decoder version.

Variant 2 : Low rate, constant query complexity perfect smooth decoder.

Locally decodable codes for hardness amplification within E. Conversion from worst-case hard Boolean function to average-case hard Boolean function using a local decoder.References: Luca Trevisan's Survey (section 3) **Theme 3 : Pseudo-randomness**- 6 meetings- Meeting 16 : Wed, Mar 11, 02:00 pm-04:00 pm - Jayalal Sarma
- Meeting 17 : Fri, Mar 13, 02:00 pm-04:00 pm -
- Meeting 18 : Wed, Mar 18, 02:00 pm-04:00 pm -
- Meeting 19 : Fri, Mar 20, 02:00 pm-04:00 pm -
- Meeting 20 : Wed, Mar 25, 02:00 pm-04:00 pm -
- Meeting 21 : Fri, Mar 27, 02:00 pm-04:00 pm -

Quest for explicit constructions. General derandomization framework and pseudorandomness. Overview of pseudo-random objects that we will see in this course. <br> Randomized approx algorithm for MAXCUT. Observation about Pairwise independence. Pairwise independence and Hadamard code. Derandomizing the MAXCUT approx algorithm. Pairwise independence on larger domains. Hash Families, pairwise independence property. References Exercises Reading Quest for explicit constructions. General derandomization framework and pseudorandomness. Overview of pseudo-random objects that we will see in this course.

Randomized approx algorithm for MAXCUT. Observation about Pairwise independence. Pairwise independence and Hadamard code. Derandomizing the MAXCUT approx algorithm. Pairwise independence on larger domains. Hash Families, pairwise independence property.References: None Construction of pairwise independent hash families. A generalization to k-wise independence. Application to success probability amplification. References Exercises Reading Construction of pairwise independent hash families. A generalization to k-wise independence. Application to success probability amplification.References: None Expander graphs. Vertex expansion, boundary expansion, edge expansion. Random Graph is vertex expander with high probability. Spectral expansion. Crash course on spectra of graphs and their applications. Random walks on graphs. Significance of second largest eigen value. Application to reachability in graphs. References Exercises Reading Expander graphs. Vertex expansion, boundary expansion, edge expansion. Random Graph is vertex expander with high probability. Spectral expansion. Crash course on spectra of graphs and their applications. Random walks on graphs. Significance of second largest eigen value. Application to reachability in graphs.References: None Spectral Gap implies vertex expansion. Main observation: collision probability gets close to that of uniform distribution. <br> Spectral Gap implies edge expansion. <br> Generalization to prove Exapander Mixing Lemma. <br> A weak amplification lemma for randomized algorithms using expander mixing lemma. References Exercises Reading Spectral Gap implies vertex expansion. Main observation: collision probability gets close to that of uniform distribution.

Spectral Gap implies edge expansion.

Generalization to prove Exapander Mixing Lemma.

A weak amplification lemma for randomized algorithms using expander mixing lemma.References: None Application of expander mixing lemma to success probability amplification. Applications to undirected reachability. Outline of explicit construction of Expanders. Graph Products and Expansion. References Exercises Reading Application of expander mixing lemma to success probability amplification. Applications to undirected reachability. Outline of explicit construction of Expanders. Graph Products and Expansion.References: None Entropy measures and randomness extractors. Extractors from pairwise independent hash families. Hash families from extractors. Extractors vs Expanders. References Exercises Reading Entropy measures and randomness extractors. Extractors from pairwise independent hash families. Hash families from extractors. Extractors vs Expanders.References: None **Theme 4 : Fourier Analysis of Boolean Functions**- 6 meetings- Meeting 22 : Wed, Apr 08, 02:00 pm-04:00 pm -
- Meeting 23 : Fri, Apr 10, 02:00 pm-04:00 pm -
- Meeting 24 : Wed, Apr 15, 02:00 pm-04:00 pm -
- Meeting 25 : Fri, Apr 17, 02:00 pm-04:00 pm -
- Meeting 26 : Wed, Apr 22, 02:00 pm-04:00 pm -
- Meeting 27 : Fri, Apr 24, 02:00 pm-04:00 pm -

Fourier Series: Weyl's Equidistribution References www.math.umn.edu/~garrett/m/mfms/notes...14/04_Fourier-Weyl.pdf Exercises Reading Fourier Series: Weyl's EquidistributionReferences: www.math.umn.edu/~garrett/m/mfms/notes...14/04_Fourier-Weyl.pdf Introduction to Fourier Transforms References Exercises Reading Introduction to Fourier TransformsReferences: None Introduction to Fourier Transform: Fourier Transform over Finite Abelian Groups References math.stanford.edu/~thiem/courses/156S/m156notes.pdf Exercises Reading Introduction to Fourier Transform: Fourier Transform over Finite Abelian GroupsReferences: math.stanford.edu/~thiem/courses/156S/m156notes.pdf Fourier Analysis over Lattices References www.cims.nyu.edu/~regev/papers/cvpconp.pdf http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2009/ Exercises Reading Fourier Analysis over LatticesReferences: www.cims.nyu.edu/~regev/papers/cvpconp.pdf http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2009/ Fourier Analysis of Boolean Functions: Goldreich-Levin theorem and application to learning sparse fourier representations References https://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/ http://www.tau.ac.il/~mansour/papers/fourier-survey.ps.gz Exercises Reading Fourier Analysis of Boolean Functions: Goldreich-Levin theorem and application to learning sparse fourier representationsReferences: https://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/ http://www.tau.ac.il/~mansour/papers/fourier-survey.ps.gz Fourier Analysis of Boolean Functions: Invariance Principle and the proof of Berry-Esseen inequality References http://www.contrib.andrew.cmu.edu/~ryanod/?tag=berry-esseen-theorem Exercises Reading Fourier Analysis of Boolean Functions: Invariance Principle and the proof of Berry-Esseen inequalityReferences: http://www.contrib.andrew.cmu.edu/~ryanod/?tag=berry-esseen-theorem **Theme 5 : Course Project Presentations**- 15 meetings- Meeting 28 : Sat, Apr 11, 09:00 am-09:45 pm - Purnata Ghosal
- Meeting 29 : Sat, Apr 11, 09:45 am-10:30 am - Meenakshi Ray
- Meeting 30 : Sat, Apr 11, 10:30 am-11:15 am - Raghavendra Kiran
- Meeting 31 : Sat, Apr 11, 11:15 am-12:00 pm - Naga Varun Shetty
- Meeting 32 : Sat, Apr 11, 01:30 pm-02:15 pm - Astha Chauhan
- Meeting 33 : Sat, Apr 11, 02:15 pm-03:00 pm - Parshuram
- Meeting 34 : Sat, Apr 11, 03:00 pm-04:15 pm - Shreyas Shetty & Abhishek Ghose
- Meeting 35 : Sat, Apr 18, 09:00 am-09:45 am - Aahlad Manas
- Meeting 36 : Sat, Apr 18, 09:45 am-11:00 am - Ameya Panse & Samir Otiv
- Meeting 37 : Sat, Apr 18, 11:00 am-11:45 am - Rajdeep Bhattacharya
- Meeting 38 : Sat, Apr 18, 11:45 am-12:30 pm - Srinivasan R.
- Meeting 39 : Sat, Apr 18, 02:00 pm-03:15 pm - Mitali Bafna & Vidya Ramaswamy
- Meeting 40 : Sat, Apr 18, 03:15 pm-04:00 pm - Kaushik Garikipati
- Meeting 41 : Sat, Apr 18, 04:00 pm-04:45 pm - Aounon Kumar
- Meeting 42 : Sat, Apr 25, 10:00 am-10:45 am - Kartik Gupta

Complexity of Computational Problems in Coding Theory. <br> See <a href="http://people.csail.mit.edu/madhu/FT01/scribe/lect20.ps">here</a>, <a href="http://users.cms.caltech.edu/~umans/522/lec11.ps">here</a> and <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.6904">here</a>. References Exercises Reading References: None <a href="http://www.ee.caltech.edu/EE/Faculty/rjm/papers/RSD-JPL.pdf">Guruswami-Sudan Algorithm, improvements</a> References Exercises Reading References: None Expander Codes and their applications - See <a href="http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.pdf">here</a> and <a href="http://www.cs.yale.edu/homes/spielman/561/lect12-09.pdf">here</a> References Exercises Reading References: None <a href="http://www.cse.ust.hk/faculty/cding/JOURNALS/jucs97.pdf">Secret Sharing Schemes and Error Correcting Codes</a> References Exercises Reading References: None <a href="http://www.wisdom.weizmann.ac.il/~feige/mypapers/santaclaus.pdf">On Allocations that Maximize Fairness</a> References Exercises Reading References: None <a href="http://arxiv.org/abs/0903.0544">A constructive proof of the general Lovasz Local Lemma</a> References Exercises Reading References: None <a href="http://www.cs.umd.edu/~barna/focs10.pdf">New Constructive Aspects of the Lovasz Local Lemma</a> References Exercises Reading References: None <a href="http://arxiv.org/abs/1407.6692">2-Server PIR with sub-polynomial communication</a> References Exercises Reading References: None <a href="http://arxiv.org/abs/0901.2529">Extensions to Method of Multiplicities & Applications.</a> References Exercises Reading References: None <a href="http://arxiv.org/abs/1203.5747">Constructive Discrepancy Minimization by Walking on The Edges</a> References Exercises Reading References: None <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.147&rep=rep1&type=pdf">Improved bounds and algorithms for hypergraph two-coloring</a> References Exercises Reading References: None <a href="http://www.ccs.neu.edu/home/viola/papers/eh.pdf">The complexity of distributions</a> References Exercises Reading References: None <a href="http://tau.ac.il/~nogaa/PDFS/aghp4.pdf">Almost k-wise independent sample space constructions and lower bounds</a> References Exercises Reading References: None <a href=" http://www.ccs.neu.edu/home/viola/papers/gen2.pdf">Pseudorandom bits for polynomials</a> References Exercises Reading References: None <a href="http://www.cs.toronto.edu/~mbraverm/FoolAC0v7.pdf">Polylogarithmic Independence Fools Constant Depth Polysize circuits</a> References Exercises Reading References: None