CS6845 - Modern Techniques in Theory of Computation

Meetings  

• Theme 1 : Probability Toolkit - 6 meetings

  • Meeting 01 : Wed, Jan 14, 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

  • Meeting 02 : Fri, Jan 16, 02:00 pm-04:00 pm - Rajsekar Manokaran

  Conditional probability spaces; Martingales; Azuma-Hoeffding inequalities.

  References
  Exercises
  Reading

  Conditional probability spaces; Martingales; Azuma-Hoeffding inequalities.
  

  References:

  None

  • Meeting 03 : Wed, Jan 21, 02:00 pm-04:00 pm - Rajsekar Manokaran

  Application of Martingales: analysing coin tossing protocols.

  References
  Exercises
  Reading

  Application of Martingales: analysing coin tossing protocols.
  

  References:

  None

  • Meeting 04 : Fri, Jan 23, 02:00 pm-04:00 pm - Rajsekar Manokaran

  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 graphs
  

  References:

  Paper on Coin-Tossing and Martingales

  • Meeting 05 : Wed, Jan 28, 02:00 pm-04:00 pm - Rajsekar Manokaran

  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 systems
  

  References:

  Book on the Discrepancy Method by Chazelle; Chapter 1

  • Meeting 06 : Fri, Jan 30, 02:00 pm-04:00 pm - Rajsekar Manokaran

  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
  

  References:

  Alistair Sinclair's lecture notes; Original paper on routing protocols

• Theme 2 : Algorithmic Coding Theory - 9 meetings

  • Meeting 07 : Wed, Feb 04, 02:00 pm-04: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:	Venkat Guruswami's Notes on Entropy

  • Meeting 08 : Fri, Feb 06, 03:00 pm-05:00 pm - Jayalal Sarma

  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.

  • Meeting 09 : Wed, Feb 11, 02:00 pm-04:00 pm - Jayalal Sarma

  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.

  • Meeting 10 : Fri, Feb 13, 03:00 pm-05:00 pm - Jayalal Sarma

  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

  • Meeting 11 : Wed, Feb 18, 02:00 pm-04:00 pm - Jayalal Sarma

  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. A
  

  References:	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.

  • Meeting 12 : Fri, Feb 20, 03:00 pm-05:00 pm - Jayalal Sarma

  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.

  • Meeting 13 : Wed, Feb 25, 02:00 pm-04:00 pm - Jayalal Sarma

  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

  • Meeting 14 : Fri, Feb 27, 02:00 pm-04:00 pm - Jayalal Sarma

  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)

  • Meeting 15 : Mon, Mar 02, 03:00 pm-05:00 pm - Jayalal Sarma

  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

  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

  • Meeting 17 : Fri, Mar 13, 02:00 pm-04:00 pm -

  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

  • Meeting 18 : Wed, Mar 18, 02:00 pm-04:00 pm -

  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

  • Meeting 19 : Fri, Mar 20, 02:00 pm-04:00 pm -

  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

  • Meeting 20 : Wed, Mar 25, 02:00 pm-04:00 pm -

  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

  • Meeting 21 : Fri, Mar 27, 02:00 pm-04:00 pm -

  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 -

  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 Equidistribution
  

  References:

  www.math.umn.edu/~garrett/m/mfms/notes...14/04_Fourier-Weyl.pdf

  • Meeting 23 : Fri, Apr 10, 02:00 pm-04:00 pm -

  Introduction to Fourier Transforms

  References
  Exercises
  Reading

  Introduction to Fourier Transforms
  

  References:

  None

  • Meeting 24 : Wed, Apr 15, 02:00 pm-04:00 pm -

  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 Groups
  

  References:

  math.stanford.edu/~thiem/courses/156S/m156notes.pdf

  • Meeting 25 : Fri, Apr 17, 02:00 pm-04:00 pm -

  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 Lattices
  

  References:

  www.cims.nyu.edu/~regev/papers/cvpconp.pdf http://www.cims.nyu.edu/~regev/teaching/lattices_fall_2009/

  • Meeting 26 : Wed, Apr 22, 02:00 pm-04:00 pm -

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

  • Meeting 27 : Fri, Apr 24, 02:00 pm-04:00 pm -

  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 inequality
  

  References:

  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

  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

  Complexity of Computational Problems in Coding Theory.
  See here, here and here.
  

  References:

  None

  • Meeting 29 : Sat, Apr 11, 09:45 am-10:30 am - Meenakshi Ray

  <a href="http://www.ee.caltech.edu/EE/Faculty/rjm/papers/RSD-JPL.pdf">Guruswami-Sudan Algorithm, improvements</a>

  References
  Exercises
  Reading

  Guruswami-Sudan Algorithm, improvements
  

  References:

  None

  • Meeting 30 : Sat, Apr 11, 10:30 am-11:15 am - Raghavendra Kiran

  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

  Expander Codes and their applications - See here and here
  

  References:

  None

  • Meeting 31 : Sat, Apr 11, 11:15 am-12:00 pm - Naga Varun Shetty

  <a href="http://www.cse.ust.hk/faculty/cding/JOURNALS/jucs97.pdf">Secret Sharing Schemes and Error Correcting Codes</a>

  References
  Exercises
  Reading

  Secret Sharing Schemes and Error Correcting Codes
  

  References:

  None

  • Meeting 32 : Sat, Apr 11, 01:30 pm-02:15 pm - Astha Chauhan

  <a href="http://www.wisdom.weizmann.ac.il/~feige/mypapers/santaclaus.pdf">On Allocations that Maximize Fairness</a>

  References
  Exercises
  Reading

  On Allocations that Maximize Fairness
  

  References:

  None

  • Meeting 33 : Sat, Apr 11, 02:15 pm-03:00 pm - Parshuram

  <a href="http://arxiv.org/abs/0903.0544">A constructive proof of the general Lovasz Local Lemma</a>

  References
  Exercises
  Reading

  A constructive proof of the general Lovasz Local Lemma
  

  References:

  None

  • Meeting 34 : Sat, Apr 11, 03:00 pm-04:15 pm - Shreyas Shetty & Abhishek Ghose

  <a href="http://www.cs.umd.edu/~barna/focs10.pdf">New Constructive Aspects of the Lovasz Local Lemma</a>

  References
  Exercises
  Reading

  New Constructive Aspects of the Lovasz Local Lemma
  

  References:

  None

  • Meeting 35 : Sat, Apr 18, 09:00 am-09:45 am - Aahlad Manas

  <a href="http://arxiv.org/abs/1407.6692">2-Server PIR with sub-polynomial communication</a>

  References
  Exercises
  Reading

  2-Server PIR with sub-polynomial communication
  

  References:

  None

  • Meeting 36 : Sat, Apr 18, 09:45 am-11:00 am - Ameya Panse & Samir Otiv

  <a href="http://arxiv.org/abs/0901.2529">Extensions to Method of Multiplicities & Applications.</a>

  References
  Exercises
  Reading

  Extensions to Method of Multiplicities & Applications.
  

  References:

  None

  • Meeting 37 : Sat, Apr 18, 11:00 am-11:45 am - Rajdeep Bhattacharya

  <a href="http://arxiv.org/abs/1203.5747">Constructive Discrepancy Minimization by Walking on The Edges</a>

  References
  Exercises
  Reading

  Constructive Discrepancy Minimization by Walking on The Edges
  

  References:

  None

  • Meeting 38 : Sat, Apr 18, 11:45 am-12:30 pm - Srinivasan R.

  <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

  Improved bounds and algorithms for hypergraph two-coloring
  

  References:

  None

  • Meeting 39 : Sat, Apr 18, 02:00 pm-03:15 pm - Mitali Bafna & Vidya Ramaswamy

  <a href="http://www.ccs.neu.edu/home/viola/papers/eh.pdf">The complexity of distributions</a>

  References
  Exercises
  Reading

  The complexity of distributions
  

  References:

  None

  • Meeting 40 : Sat, Apr 18, 03:15 pm-04:00 pm - Kaushik Garikipati

  <a href="http://tau.ac.il/~nogaa/PDFS/aghp4.pdf">Almost k-wise independent sample space constructions and lower bounds</a>

  References
  Exercises
  Reading

  Almost k-wise independent sample space constructions and lower bounds
  

  References:

  None

  • Meeting 41 : Sat, Apr 18, 04:00 pm-04:45 pm - Aounon Kumar

  <a href=" http://www.ccs.neu.edu/home/viola/papers/gen2.pdf">Pseudorandom bits for polynomials</a>

  References
  Exercises
  Reading

  Pseudorandom bits for polynomials
  

  References:

  None

  • Meeting 42 : Sat, Apr 25, 10:00 am-10:45 am - Kartik Gupta

  <a href="http://www.cs.toronto.edu/~mbraverm/FoolAC0v7.pdf">Polylogarithmic Independence Fools Constant Depth Polysize circuits</a>

  References
  Exercises
  Reading

  Polylogarithmic Independence Fools Constant Depth Polysize circuits
  

  References:

  None