CS6845 - Pseudorandomness

Meetings  

• Theme 1 : Pseudorandomness: Overview - 13 meetings

  • Meeting 01 : Wed, Jan 16, 10:00 am-10:50 am

  Administrative announcements.

  References
  Exercises
  Reading

  Administrative announcements.
  

  References:

  None

  • Meeting 02 : Thu, Jan 17, 08:00 am-08:50 am

  Examples of randomized algorithms: Max Cut. Polynomial identity Testing.

  References	Vadhan's survey.
  Exercises
  Reading	For more details about the parallel algorithm for matching read: Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani: "Matching is as easy as matrix inversion". Combinatorica 7(1): 105-113 (1987)

  Examples of randomized algorithms: Max Cut. Polynomial identity Testing.
  

  References:	Vadhan's survey.
  Reading:	For more details about the parallel algorithm for matching read: Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani: "Matching is as easy as matrix inversion". Combinatorica 7(1): 105-113 (1987)

  • Meeting 03 : Fri, Jan 18, 04:50 pm-05:40 pm

  Application to matching. Application to primality. Fingerprinting.

  References
  Exercises
  Reading

  Application to matching. Application to primality. Fingerprinting.
  

  References:

  None

  • Meeting 04 : Tue, Jan 22, 11:00 am-11:50 am

  Lecture cancelled due to instructor's unavailability.

  References
  Exercises
  Reading

  Lecture cancelled due to instructor's unavailability.
  

  References:

  None

  • Meeting 05 : Wed, Jan 23, 10:00 am-10:50 am

  Randomness in computation. Definition of randomized complexity classes.

  References
  Exercises
  Reading

  Randomness in computation. Definition of randomized complexity classes.
  

  References:

  None

  • Meeting 06 : Thu, Jan 24, 08:00 am-08:50 am

  Reducing the error probability. Pairwise independent random bits.

  References
  Exercises
  Reading

  Reducing the error probability. Pairwise independent random bits.
  

  References:

  None

  • Meeting 07 : Fri, Jan 25, 08:00 am-08:50 am

  Derandomized max cut algorithm using pairwise independent bits. Pairwise independent hash families. k-wise independence.

  References
  Exercises
  Reading

  Derandomized max cut algorithm using pairwise independent bits. Pairwise independent hash families. k-wise independence.
  

  References:

  None

  • Meeting 08 : Tue, Jan 29, 11:00 am-11:50 am

  Conditional Expectation. USTCONN

  References
  Exercises
  Reading

  Conditional Expectation. USTCONN
  

  References:

  None

  • Meeting 09 : Wed, Jan 30, 10:00 am-10:50 am

  Undirected s-t connectivity (UST CONN). Introduction to Expanders. Vertex Exapnasion.

  References
  Exercises
  Reading

  Undirected s-t connectivity (UST CONN). Introduction to Expanders. Vertex Exapnasion.
  

  References:

  None

  • Meeting 10 : Tue, Feb 19, 11:00 am-11:50 am

  Pseudorandom generators: Computational Indistinguishability, Definition.

  References
  Exercises
  Reading

  Pseudorandom generators: Computational Indistinguishability, Definition.
  

  References:

  None

  • Meeting 11 : Wed, Feb 20, 10:00 am-10:50 am

  Pseudorandom generators: Relation to one-way functions (statement only). Hybrid argument. Next bit predictor (definition only)

  References
  Exercises
  Reading

  Pseudorandom generators: Relation to one-way functions (statement only). Hybrid argument. Next bit predictor (definition only)
  

  References:

  None

  • Meeting 12 : Thu, Feb 21, 08:00 am-08:50 am

  PRGs from hard functions: Next bit unpredictability is equivalent to PRG. Nisan-Wigderson Designs

  References
  Exercises
  Reading

  PRGs from hard functions: Next bit unpredictability is equivalent to PRG. Nisan-Wigderson Designs
  

  References:

  None

  • Meeting 13 : Fri, Feb 22, 02:00 pm-02:50 pm

  PRGs from hard functions: Nisan Wigderson generator.

  References
  Exercises
  Reading

  PRGs from hard functions: Nisan Wigderson generator.
  

  References:

  None

• Theme 2 : Error Correcting Codes - 21 meetings

  • Meeting 14 : Tue, Feb 26, 11:00 am-11:50 am

  Introduction to Error Correcting Codes. Shannon's Noisy channel encoding theorem (statement only). Basic definitions.

  References	https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  Exercises
  Reading

  Introduction to Error Correcting Codes. Shannon's Noisy channel encoding theorem (statement only). Basic definitions.
  

  References:

  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

  • Meeting 15 : Wed, Feb 27, 10:00 am-10:50 am

  Basic parameters of error correcting codes: Dimension, distance. Hamming code. Binary linear codes. Hamming bound.

  References	https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  Exercises
  Reading

  Basic parameters of error correcting codes: Dimension, distance. Hamming code. Binary linear codes. Hamming bound.
  

  References:

  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

  • Meeting 16 : Thu, Feb 28, 08:00 am-08:50 am

  Linear Codes. Properties of linear codes. Generator matrix. Parity Check matrix. Dual codes.

  References	https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  Exercises
  Reading

  Linear Codes. Properties of linear codes. Generator matrix. Parity Check matrix. Dual codes.
  

  References:

  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

  • Meeting 17 : Thu, Feb 28, 05:00 pm-06:35 pm

  Singleton Bound. Reed-Solomon code.

  References	https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  Exercises
  Reading

  Singleton Bound. Reed-Solomon code.
  

  References:

  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

  • Meeting 18 : Fri, Mar 01, 02:00 pm-02:50 pm

  Reed-Solomon Code. Unique decoding Reed Solomon code: Challenges.

  References	https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  Exercises
  Reading

  Reed-Solomon Code. Unique decoding Reed Solomon code: Challenges.
  

  References:

  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

  • Meeting 19 : Tue, Mar 05, 11:00 am-11:50 am

  Unique decoding of Reed-Solomon codes : Berlekamp-Welch algorithm. Proof.

  References	https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  Exercises
  Reading

  Unique decoding of Reed-Solomon codes : Berlekamp-Welch algorithm. Proof.
  

  References:

  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

  • Meeting 20 : Wed, Mar 06, 10:00 am-10:50 am

  Unique decoding (contd). Application to average case hardness of permanent.

  References	https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  Exercises
  Reading

  Unique decoding (contd). Application to average case hardness of permanent.
  

  References:

  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

  • Meeting 21 : Thu, Mar 07, 08:00 am-08:50 am

  List decoding of RS codes. Toy problem.

  References	https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  Exercises
  Reading

  List decoding of RS codes. Toy problem.
  

  References:

  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

  • Meeting 22 : Thu, Mar 07, 05:00 pm-06:30 pm

  List Decoding- Sudan's agorithm

  References
  Exercises
  Reading

  List Decoding- Sudan's agorithm
  

  References:

  None

  • Meeting 23 : Fri, Mar 08, 02:00 pm-02:50 pm

  Applications to Average case hardness. The permanent function. Average case complexity of permanent.

  References	https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
  Exercises
  Reading

  Applications to Average case hardness. The permanent function. Average case complexity of permanent.
  

  References:

  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/

  • Meeting 24 : Tue, Mar 12, 11:00 am-11:50 am

  Average case complexity of permanent (contd). Reducing alphabets in error correcting codes.

  References
  Exercises
  Reading

  Average case complexity of permanent (contd). Reducing alphabets in error correcting codes.
  

  References:

  None

  • Meeting 25 : Wed, Mar 13, 10:00 am-10:50 am

  Reed-Muller codes. Concatenation codes.

  References
  Exercises
  Reading

  Reed-Muller codes. Concatenation codes.
  

  References:

  None

  • Meeting 26 : Thu, Mar 14, 08:00 am-08:50 am

  Locally decodable codes. Definitions. Private information retrieval schemes.

  References
  Exercises
  Reading

  Locally decodable codes. Definitions. Private information retrieval schemes.
  

  References:

  None

  • Meeting 27 : Thu, Mar 14, 05:00 pm-06:30 pm

  Perfectly Smooth decodable codes imply PIR schemes and Locally decodable codes. Local decoding of Hadamard codes. Reed Muller codes.

  References
  Exercises
  Reading

  Perfectly Smooth decodable codes imply PIR schemes and Locally decodable codes. Local decoding of Hadamard codes. Reed Muller codes.
  

  References:

  None

  • Meeting 28 : Fri, Mar 15, 02:00 pm-02:50 pm

  Apllication of locally decodable codes to average case hardness of languages in EXP. Local List decoding: Definitions.

  References
  Exercises
  Reading

  Apllication of locally decodable codes to average case hardness of languages in EXP. Local List decoding: Definitions.
  

  References:

  None

  • Meeting 29 : Tue, Mar 19, 11:00 am-11:50 am

  Examples of local list decoding algorithms: Goldreich Levin Theorem, other codes with better rates. Applications to average case hardness.

  References
  Exercises
  Reading

  Examples of local list decoding algorithms: Goldreich Levin Theorem, other codes with better rates. Applications to average case hardness.
  

  References:

  None

  • Meeting 30 : Wed, Mar 20, 10:00 am-10:50 am

  Proof of Goldreich Levin Theorem.

  References
  Exercises
  Reading

  Proof of Goldreich Levin Theorem.
  

  References:

  None

  • Meeting 31 : Fri, Mar 29, 02:00 pm-02:50 pm

  Lecture cancelled

  References
  Exercises
  Reading

  Lecture cancelled
  

  References:

  None

  • Meeting 32 : Tue, Apr 02, 11:00 am-11:50 am

  Hardcore predicates using Goldreich-Levin

  References
  Exercises
  Reading

  Hardcore predicates using Goldreich-Levin
  

  References:

  None

  • Meeting 33 : Wed, Apr 03, 10:00 am-10:50 am

  Hardcore predicates using Goldreich Levin

  References
  Exercises
  Reading

  Hardcore predicates using Goldreich Levin
  

  References:

  None

  • Meeting 34 : Fri, Apr 05, 02:00 pm-02:50 pm

  No lecture

  References
  Exercises
  Reading

  No lecture
  

  References:

  None

• Theme 3 : Expanders - 10 meetings

  • Meeting 35 : Thu, Jan 31, 08:00 am-08:50 am

  Vertex Expanders: Existence. Challenges in construction.

  References	Vadhan's survey. The <a href="https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes5.pdf"> lecture notes</a> by He Sun gives a detailed account. The <a href="https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws10/EG/WS10.html"> lecture notes on expander graphs </a> by He Sun is also a very good reference.
  Exercises
  Reading

  Vertex Expanders: Existence. Challenges in construction.
  

  References:

  Vadhan's survey. The lecture notes by He Sun gives a detailed account. The lecture notes on expander graphs by He Sun is also a very good reference.

  • Meeting 36 : Fri, Feb 01, 08:00 am-08:50 am

  Spectral vs Vertex Expansion.

  References	Vadhan's survey is a general reference for the whole theme. The <a href="https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes5.pdf"> lecture notes</a> by He Sun gives a detailed account. The <a href="https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws10/EG/WS10.html"> lecture notes on expander graphs </a> by He Sun is also a very good reference.
  Exercises
  Reading

  Spectral vs Vertex Expansion.
  

  References:

  Vadhan's survey is a general reference for the whole theme. The lecture notes by He Sun gives a detailed account. The lecture notes on expander graphs by He Sun is also a very good reference.

  • Meeting 37 : Tue, Feb 05, 11:00 am-11:50 am

  Spectral vs Vertex expansion. Edge Expansion: Mixing Lemma.

  References	Vadhan's survey is a general reference for the whole theme. The <a href="https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes5.pdf"> lecture notes</a> by He Sun gives a detailed account. The <a href="https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws10/EG/WS10.html"> lecture notes on expander graphs </a> by He Sun is also a very good reference.
  Exercises
  Reading

  Spectral vs Vertex expansion. Edge Expansion: Mixing Lemma.
  

  References:

  Vadhan's survey is a general reference for the whole theme. The lecture notes by He Sun gives a detailed account. The lecture notes on expander graphs by He Sun is also a very good reference.

  • Meeting 38 : Wed, Feb 06, 10:00 am-10:50 am

  Edge Expansion: Mixing Lemma. Random walks in expanders.

  References	Vadhan's survey is a general reference for the whole theme. The <a href="https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws10/EG/WS10.html"> lecture notes on expander graphs </a> by He Sun is a very good reference.
  Exercises
  Reading

  Edge Expansion: Mixing Lemma. Random walks in expanders.
  

  References:

  Vadhan's survey is a general reference for the whole theme. The lecture notes on expander graphs by He Sun is a very good reference.

  • Meeting 39 : Thu, Feb 07, 08:00 am-08:50 am

  Random walks in expanders. Hittting property of random walks.

  References
  Exercises
  Reading

  Random walks in expanders. Hittting property of random walks.
  

  References:

  None

  • Meeting 40 : Fri, Feb 08, 08:00 am-08:50 am

  Construction of explicit expanders: Examples without proof. Building expanders from given graphs. Graph products: Squaring, Tensor product.

  References
  Exercises
  Reading	These <a href="https://www.math.uwaterloo.ca/~hwolkowi/henry/reports/kronthesisschaecke04.pdf"> notes by Kathrin Schaecke gives a more detailed introduction to Kronecker product (also known as tensor product) of matrices

  Construction of explicit expanders: Examples without proof. Building expanders from given graphs. Graph products: Squaring, Tensor product.
  

  References:	None
  Reading:	These notes by Kathrin Schaecke gives a more detailed introduction to Kronecker product (also known as tensor product) of matrices

  • Meeting 41 : Tue, Feb 12, 11:00 am-11:50 am

  Tensor product. Zig Zag product.

  References
  Exercises
  Reading

  Tensor product. Zig Zag product.
  

  References:

  None

  • Meeting 42 : Wed, Feb 13, 10:00 am-10:50 am

  Zig Zag product.

  References
  Exercises
  Reading

  Zig Zag product.
  

  References:

  None

  • Meeting 43 : Thu, Feb 14, 08:00 am-08:50 am

  Quiz 1

  References
  Exercises
  Reading

  Quiz 1
  

  References:

  None

  • Meeting 44 : Fri, Feb 15, 02:00 pm-02:50 pm

  Using Zig-Zag product.

  References
  Exercises
  Reading

  Using Zig-Zag product.
  

  References:

  None

• Theme 4 : Fourier analysis and Extractors - 11 meetings

  • Meeting 45 : Thu, Apr 04, 08:00 am-08:50 am

  Introduction to Fourier Analysis. BLR Linearity Test

  References
  Exercises
  Reading

  Introduction to Fourier Analysis. BLR Linearity Test
  

  References:

  None

  • Meeting 46 : Fri, Apr 05, 08:00 am-08:50 am

  BLR Linearity Test. Influence of Variables.

  References
  Exercises
  Reading

  BLR Linearity Test. Influence of Variables.
  

  References:

  None

  • Meeting 47 : Tue, Apr 09, 11:00 am-11:50 am

  Poincare Inequality, FKN Theorem (without Proof). Spectral concentration. A Fourier view of Goldreich Levin. Decision trees.

  References
  Exercises
  Reading

  Poincare Inequality, FKN Theorem (without Proof). Spectral concentration. A Fourier view of Goldreich Levin. Decision trees.
  

  References:

  None

  • Meeting 48 : Wed, Apr 10, 10:00 am-10:50 am

  Spectral concentration of decision trees.

  References
  Exercises
  Reading

  Spectral concentration of decision trees.
  

  References:

  None

  • Meeting 49 : Thu, Apr 11, 08:00 am-08:50 am

  Fourier based Goldreich Levin

  References
  Exercises
  Reading

  Fourier based Goldreich Levin
  

  References:

  None

  • Meeting 50 : Thu, Apr 11, 05:00 pm-06:30 pm

  Hardcore Predicates

  References
  Exercises
  Reading

  Hardcore Predicates
  

  References:

  None

  • Meeting 51 : Fri, Apr 12, 02:00 pm-02:50 pm

  Extractors. Definition

  References
  Exercises
  Reading

  Extractors. Definition
  

  References:

  None

  • Meeting 52 : Tue, Apr 16, 11:00 am-11:50 am

  Left over Hash lemma.

  References
  Exercises
  Reading

  Left over Hash lemma.
  

  References:

  None

  • Meeting 53 : Tue, Apr 23, 11:00 am-11:50 am

  Presentations.

  References
  Exercises
  Reading

  Presentations.
  

  References:

  None

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

  Presentation.

  References
  Exercises
  Reading

  Presentation.
  

  References:

  None

  • Meeting 55 : Thu, Apr 25, 08:00 am-08:50 am

  Sum of d epsilon bias spaces fools degree d polynomials.

  References
  Exercises
  Reading

  Sum of d epsilon bias spaces fools degree d polynomials.
  

  References:

  None