CS6845 - Pseudorandomness

Meetings  

• Theme 1 : Revision of Probabilistic Techniques - 4 meetings

  • Meeting 01 : Mon, Jan 09, 08:00 am-08:50 am

  The derandomization question: Polynomial identity testing. Administrative announcements.

  References
  Exercises
  Reading

  The derandomization question: Polynomial identity testing. Administrative announcements.
  

  References:

  None

  • Meeting 02 : Tue, Jan 10, 12:00 pm-12:50 pm

  Linearity of expectation. Markov's inequality, Chebyshev's inequality, Chernoff's bound. Some applications.

  References
  Exercises
  Reading

  Linearity of expectation. Markov's inequality, Chebyshev's inequality, Chernoff's bound. Some applications.
  

  References:

  None

  • Meeting 03 : Thu, Jan 12, 11:00 am-11:50 am

  Lovasz Local Lemma: Statement and applications. Application 1: Satisfiablity of a k-CNF formula. Application 2: Existence of a cycle whose length is 0 modulo k.

  References	"Probabilistic Method" by Alon and Spencer, Chapter on local lemma.
  Exercises
  Reading

  Lovasz Local Lemma: Statement and applications. Application 1: Satisfiablity of a k-CNF formula. Application 2: Existence of a cycle whose length is 0 modulo k.
  

  References:

  "Probabilistic Method" by Alon and Spencer, Chapter on local lemma.

  • Meeting 04 : Fri, Jan 13, 10:00 am-10:50 am

  Proof of LLL (full statement with dependency graphs).

  References	"Probabilistic Method" by Alon and Spencer, Chapter on local lemma
  Exercises
  Reading

  Proof of LLL (full statement with dependency graphs).
  

  References:

  "Probabilistic Method" by Alon and Spencer, Chapter on local lemma

• Theme 2 : Codes: constructions and applications - 20 meetings

  • Meeting 05 : Tue, Jan 17, 12:00 pm-12:50 pm

  Proof of LLL (cont'd). The derandomization question. Notion of Pseudorandom generators. Introduction to error correcting codes.

  References
  Exercises
  Reading

  Proof of LLL (cont'd). The derandomization question. Notion of Pseudorandom generators. Introduction to error correcting codes.
  

  References:

  None

  • Meeting 06 : Tue, Jan 17, 05:30 pm-06:20 pm

  Definition of Pseudorandom generators. Introduction to Error correcting codes. Shannon: Noiseless coding theorem, Noisy encoding theorem. Basic notions: distance, rate etc

  References
  Exercises
  Reading

  Definition of Pseudorandom generators. Introduction to Error correcting codes. Shannon: Noiseless coding theorem, Noisy encoding theorem. Basic notions: distance, rate etc
  

  References:

  None

  • Meeting 07 : Thu, Jan 19, 11:00 am-11:50 am

  Proof of Noisy channel coding theorem.

  References
  Exercises
  Reading

  Proof of Noisy channel coding theorem.
  

  References:

  None

  • Meeting 08 : Fri, Jan 20, 10:00 am-10:50 am

  Proof of Noisy channel coding theorem.

  References
  Exercises
  Reading

  Proof of Noisy channel coding theorem.
  

  References:

  None

  • Meeting 09 : Tue, Jan 24, 12:00 pm-12:50 pm

  Definition of error correcting codes. Distance, rate. Number of errors that can be corrected vs distance.

  References
  Exercises
  Reading

  Definition of error correcting codes. Distance, rate. Number of errors that can be corrected vs distance.
  

  References:

  None

  • Meeting 10 : Tue, Jan 24, 05:30 pm-06:30 pm

  Notion of distance rate (contd). Example Hamming code.

  References
  Exercises
  Reading

  Notion of distance rate (contd). Example Hamming code.
  

  References:

  None

  • Meeting 11 : Fri, Jan 27, 10:00 am-10:50 am

  Linear code. Generator matrix. Parity Check matrix. Distance of a code based on parity check matrix.

  References
  Exercises
  Reading

  Linear code. Generator matrix. Parity Check matrix. Distance of a code based on parity check matrix.
  

  References:

  None

  • Meeting 12 : Tue, Jan 31, 12:00 pm-12:50 pm

  Notion of dual codes. Dual code is generated by parity check matrix. Hadamrd Codes: Duals of Hamming codes. Hamming's bound. Singleton Bound.

  References
  Exercises
  Reading

  Notion of dual codes. Dual code is generated by parity check matrix. Hadamrd Codes: Duals of Hamming codes. Hamming's bound. Singleton Bound.
  

  References:

  None

  • Meeting 13 : Tue, Jan 31, 05:30 pm-06:30 pm

  Reed Solomon codes: definition and properties.

  References
  Exercises
  Reading

  Reed Solomon codes: definition and properties.
  

  References:

  None

  • Meeting 14 : Thu, Feb 02, 11:00 am-11:50 am

  The unique decoding problem. Berlekamp-Welch unique decoding algorithm for RS codes.

  References
  Exercises
  Reading

  The unique decoding problem. Berlekamp-Welch unique decoding algorithm for RS codes.
  

  References:

  None

  • Meeting 15 : Fri, Feb 03, 10:00 am-10:50 am

  The list decoding problem. List decodable codes. Johnson's bound (without proof). List decoding of RS codes. Toy problem.

  References
  Exercises
  Reading

  The list decoding problem. List decodable codes. Johnson's bound (without proof). List decoding of RS codes. Toy problem.
  

  References:

  None

  • Meeting 16 : Mon, Feb 06, 08:00 am-08:50 am

  Toy problem (contd). Sudan's list decoding algorithm: Outline.

  References
  Exercises
  Reading

  Toy problem (contd). Sudan's list decoding algorithm: Outline.
  

  References:

  None

  • Meeting 17 : Tue, Feb 07, 12:00 pm-12:50 pm

  Sudan's List decoding algorithm: proof of correctness.

  References
  Exercises
  Reading

  Sudan's List decoding algorithm: proof of correctness.
  

  References:

  None

  • Meeting 18 : Thu, Feb 09, 11:00 am-11:50 am

  An application of list decoding. Permananent function: definition and complexity status. Average case hardness of permanent- Lipton's reduction.

  References
  Exercises
  Reading

  An application of list decoding. Permananent function: definition and complexity status. Average case hardness of permanent- Lipton's reduction.
  

  References:

  None

  • Meeting 19 : Fri, Feb 10, 10:00 am-10:50 am

  Average case hardness of permanent- Cai-Pawan-Sivakumar.

  References
  Exercises
  Reading

  Average case hardness of permanent- Cai-Pawan-Sivakumar.
  

  References:

  None

  • Meeting 20 : Tue, Feb 14, 12:00 pm-12:50 pm

  Average case hardness of permanent(contd). Introduction to locally decodable codes,

  References
  Exercises
  Reading

  Average case hardness of permanent(contd). Introduction to locally decodable codes,
  

  References:

  None

  • Meeting 21 : Tue, Feb 14, 05:30 pm-06:30 pm

  Locally docadable codes and private information retrieval. Smooth decodable codes.

  References	<a href="http://www.nowpublishers.com/article/DownloadSummary/TCS-030">Survey on Locally Decodable Codes </a> by Sergey Yekhanin
  Exercises
  Reading

  Locally docadable codes and private information retrieval. Smooth decodable codes.
  

  References:

  Survey on Locally Decodable Codes by Sergey Yekhanin

  • Meeting 22 : Thu, Feb 16, 11:00 am-11:50 am

  Average case vs worst case hardness for E. Use of locally decodable codes.

  References	A <a href="https://arxiv.org/abs/cs/0409044"> survey </a> by Luca Trevisan.
  Exercises
  Reading

  Average case vs worst case hardness for E. Use of locally decodable codes.
  

  References:

  A survey by Luca Trevisan.

  • Meeting 23 : Fri, Feb 17, 10:00 am-10:50 am

  Local decoding of Hadamard codes. Local list decoding. Goldreich-Levin theorem (statement only). Applications to hard-core predicates.

  References	A <a href="https://arxiv.org/abs/cs/0409044"> survey </a> by Luca Trevisan.
  Exercises
  Reading

  Local decoding of Hadamard codes. Local list decoding. Goldreich-Levin theorem (statement only). Applications to hard-core predicates.
  

  References:

  A survey by Luca Trevisan.

  • Meeting 24 : Tue, Feb 21, 12:00 pm-12:50 pm

  Application to hard-core predicates (contd).

  References	A <a href="https://arxiv.org/abs/cs/0409044"> survey </a> by Luca Trevisan.
  Exercises
  Reading

  Application to hard-core predicates (contd).
  

  References:

  A survey by Luca Trevisan.

• Theme 3 : Explicit Constructions - 18 meetings

  • Meeting 25 : Tue, Feb 21, 05:30 pm-06:30 pm

  Explicit Constructions: Construction of pairwise independent spaces. Application.

  References	"Pseudorandomness" by Vadhan
  Exercises
  Reading

  Explicit Constructions: Construction of pairwise independent spaces. Application.
  

  References:

  "Pseudorandomness" by Vadhan

  • Meeting 26 : Thu, Feb 23, 11:00 am-11:50 am

  Definition of statistical difference and entropy. k-sources, flat-k sources. Definition of Extractors. Existence of extractors for a fixed flat-k source.

  References	"Pseudorandomness" by Vadhan
  Exercises
  Reading

  Definition of statistical difference and entropy. k-sources, flat-k sources. Definition of Extractors. Existence of extractors for a fixed flat-k source.
  

  References:

  "Pseudorandomness" by Vadhan

  • Meeting 27 : Fri, Feb 24, 10:00 am-10:50 am

  Existence of extractors with small seeds.

  References	"Pseudorandomness" by Vadhan
  Exercises
  Reading

  Existence of extractors with small seeds.
  

  References:

  "Pseudorandomness" by Vadhan

  • Meeting 28 : Mon, Feb 27, 08:00 am-08:50 am

  Strong extractors from pairwise independent hash families.

  References	"Pseudorandomness" by Vadhan
  Exercises
  Reading

  Strong extractors from pairwise independent hash families.
  

  References:

  "Pseudorandomness" by Vadhan

  • Meeting 29 : Tue, Feb 28, 05:30 pm-06:30 pm

  Cancelled.

  References
  Exercises
  Reading

  Cancelled.
  

  References:

  None

  • Meeting 30 : Thu, Mar 02, 11:00 am-11:50 am

  Graph view of extractors. Introduction to expanders. Vertex vs Spectral Expansion.

  References
  Exercises
  Reading

  Graph view of extractors. Introduction to expanders. Vertex vs Spectral Expansion.
  

  References:

  None

  • Meeting 31 : Sat, Mar 04, 11:15 am-12:15 pm

  Edge expansion. Expander mixing Lemma. Relations between different definitions of expanders.

  References
  Exercises
  Reading

  Edge expansion. Expander mixing Lemma. Relations between different definitions of expanders.
  

  References:

  None

  • Meeting 32 : Tue, Mar 07, 12:00 pm-12:50 pm

  Expander mixing Lemma. Application 1: Random walks on expanders.

  References
  Exercises
  Reading

  Expander mixing Lemma. Application 1: Random walks on expanders.
  

  References:

  None

  • Meeting 33 : Tue, Mar 07, 05:30 pm-06:30 pm

  Random Walks (contd).

  References
  Exercises
  Reading

  Random Walks (contd).
  

  References:

  None

  • Meeting 34 : Tue, Mar 14, 12:00 pm-12:50 pm

  Random Walks on Expanders

  References
  Exercises
  Reading

  Random Walks on Expanders
  

  References:

  None

  • Meeting 35 : Tue, Mar 14, 05:30 pm-06:30 pm

  Random Walks on expanders (contd). Construction of expanders. Product construction.

  References
  Exercises
  Reading

  Random Walks on expanders (contd). Construction of expanders. Product construction.
  

  References:

  None

  • Meeting 36 : Thu, Mar 16, 11:00 am-11:50 am

  Construction of Expander graphs. Product construction.

  References
  Exercises
  Reading

  Construction of Expander graphs. Product construction.
  

  References:

  None

  • Meeting 37 : Fri, Mar 17, 10:00 am-10:50 am

  Product construction (contd)

  References
  Exercises
  Reading

  Product construction (contd)
  

  References:

  None

  • Meeting 38 : Mon, Mar 20, 08:00 am-08:50 am

  Applications expanders: Undirected Reachability.

  References
  Exercises
  Reading

  Applications expanders: Undirected Reachability.
  

  References:

  None

  • Meeting 39 : Tue, Mar 21, 12:00 pm-12:50 pm

  Undirected Reachability is in deterministic Log Space.

  References
  Exercises
  Reading

  Undirected Reachability is in deterministic Log Space.
  

  References:

  None

  • Meeting 40 : Thu, Mar 23, 11:00 am-11:50 am

  Relation between extractors and expanders. Construction of extractors from expanders. More constructions of extractors. Extractors from block k sources.

  References
  Exercises
  Reading

  Relation between extractors and expanders. Construction of extractors from expanders. More constructions of extractors. Extractors from block k sources.
  

  References:

  None

  • Meeting 41 : Mon, Mar 27, 12:15 pm-01:05 pm

  Trevisan's extractor: Overview of the construction. Nisan Wigderson Pseudorandom generator.

  References
  Exercises
  Reading

  Trevisan's extractor: Overview of the construction. Nisan Wigderson Pseudorandom generator.
  

  References:

  None

  • Meeting 42 : Thu, Mar 30, 11:00 am-12:00 pm

  Trevisan's extractor: The hybrid argument.

  References	"Extractors and Pseudorandom Generators" by Luca Trevisan, JACM 2001.
  Exercises
  Reading

  Trevisan's extractor: The hybrid argument.
  

  References:

  "Extractors and Pseudorandom Generators" by Luca Trevisan, JACM 2001.

• Theme 4 : Fourier Analysis - 13 meetings

  • Meeting 43 : Fri, Mar 31, 11:00 am-11:50 am

  Trevisan's extractor (contd)

  References
  Exercises
  Reading

  Trevisan's extractor (contd)
  

  References:

  None

  • Meeting 44 : Sat, Apr 01, 09:00 am-10:00 am

  Trevisan's extractor (contd) Introduction to Fourier Analysis on the Boolean Cube. Parseval's equality.

  References
  Exercises
  Reading

  Trevisan's extractor (contd) Introduction to Fourier Analysis on the Boolean Cube. Parseval's equality.
  

  References:

  None

  • Meeting 45 : Sat, Apr 01, 10:00 am-10:45 am

  Parseval's equality. Fourier transforms of example Boolean functions. Linearity Testing: the BLR test.

  References
  Exercises
  Reading

  Parseval's equality. Fourier transforms of example Boolean functions. Linearity Testing: the BLR test.
  

  References:

  None

  • Meeting 46 : Sat, Apr 01, 11:00 am-11:30 am

  Linearity Testing: the BLR test.

  References
  Exercises
  Reading

  Linearity Testing: the BLR test.
  

  References:

  None

  • Meeting 47 : Mon, Apr 03, 08:00 am-08:50 am

  Linearity Testing: the BLR test.

  References
  Exercises
  Reading

  Linearity Testing: the BLR test.
  

  References:

  None

  • Meeting 48 : Tue, Apr 04, 12:00 pm-12:50 pm

  Learning Boolean Functions From Fourier expansion to learning.

  References
  Exercises
  Reading

  Learning Boolean Functions From Fourier expansion to learning.
  

  References:

  None

  • Meeting 49 : Tue, Apr 04, 05:30 pm-06:30 pm

  Estimating the Fourier coefficients. Low-degree learning. Fourier spectrum for decision trees.

  References
  Exercises
  Reading

  Estimating the Fourier coefficients. Low-degree learning. Fourier spectrum for decision trees.
  

  References:

  None

  • Meeting 50 : Thu, Apr 06, 11:00 am-11:50 am

  Fourier spectrum of Decision trees.

  References
  Exercises
  Reading

  Fourier spectrum of Decision trees.
  

  References:

  None

  • Meeting 51 : Fri, Apr 07, 10:00 am-10:50 am

  Fourier Spectrum of Decision trees (contd). Learning Sparse Boolean functions.

  References
  Exercises
  Reading

  Fourier Spectrum of Decision trees (contd). Learning Sparse Boolean functions.
  

  References:

  None

  • Meeting 52 : Mon, Apr 10, 08:00 am-08:50 am

  Lecture cancelled due to lack of attendees.

  References
  Exercises
  Reading

  Lecture cancelled due to lack of attendees.
  

  References:

  None

  • Meeting 53 : Tue, Apr 11, 12:00 pm-12:50 pm

  Learning Sparse Boolean functions. Reduction to the Goldreich-Levin Theorem. Learning heavy Fourier Coefficients: Proof of Goldreich-Levin-Theorem.

  References
  Exercises
  Reading

  Learning Sparse Boolean functions. Reduction to the Goldreich-Levin Theorem. Learning heavy Fourier Coefficients: Proof of Goldreich-Levin-Theorem.
  

  References:

  None

  • Meeting 54 : Wed, Apr 12, 10:00 am-10:50 am

  Fourier Concentration of DNF formulas. Learning DNFs.

  References
  Exercises
  Reading

  Fourier Concentration of DNF formulas. Learning DNFs.
  

  References:

  None

  • Meeting 55 : Fri, Apr 21, 10:00 am-10:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

• Theme 5 : Pseudorandomness: A unified view - 4 meetings

  • Meeting 56 : Thu, Apr 13, 11:00 am-11:50 am

  Unified view of Pseudorandomness: LIST, the central object. Expander, List decodable codes, Extractors in terms of LIST.

  References
  Exercises
  Reading

  Unified view of Pseudorandomness: LIST, the central object. Expander, List decodable codes, Extractors in terms of LIST.
  

  References:

  None

  • Meeting 57 : Mon, Apr 17, 08:00 am-08:50 am

  Unified view (contd)

  References
  Exercises
  Reading

  Unified view (contd)
  

  References:

  None

  • Meeting 58 : Tue, Apr 18, 12:00 pm-12:50 pm

  Pseudorandom generators -1

  References
  Exercises
  Reading

  Pseudorandom generators -1
  

  References:

  None

  • Meeting 59 : Tue, Apr 18, 06:15 pm-07:15 pm

  Pseduorandom generators - 2

  References
  Exercises
  Reading

  Pseduorandom generators - 2
  

  References:

  None

• Theme 6 : Evaluation - 2 meetings

  • Meeting 60 : Sat, Mar 04, 09:00 am-11:00 am

  Mid semester exam. Syllabus: Lectures 1-30.

  References
  Exercises
  Reading

  Mid semester exam. Syllabus: Lectures 1-30.
  

  References:

  None

  • Meeting 61 : Mon, Apr 24, 01:00 pm-04:00 pm

  End Sem. Syllabus - Everything done in the class.

  References
  Exercises
  Reading

  End Sem. Syllabus - Everything done in the class.
  

  References:

  None