Activities

This page will list down the course activities in addition to the lectures.

Problem Sets :

  • Problem Set 1, Jan 14, (Sent on Jan 15) Deadline: Jan 26
  • Problem Set 2, Feb 08 (delayed, sent on 10 Feb) , Deadline: Feb 24 (extend as per request)
  • Problem Set 3, Feb 24 (Delayed, sent on 02 Mar), Deadline: Mar 19
  • Problem Set 4, Apr 05, Deadline: Apr 19
  • Problem Set 5, Apr 15, Deadline: May 04 (Optional)

Presentation:

  1. Vivek V. P. A constructive proof of Lovasz' Local Lemma , Date: TBA.
  2. Om Prakash Short paths in expander graphs
  3. Goovwanth An elementary construction of constant-degree expanders
  4. Vipin Pseudorandom bits for polynomials
  5. Santhoshini Linear-algebraic list decoding for variants of Reed-Solomon codes
  6. Aakash The sum of d small-bias generators fools polynomials of degree d.
  7. Shom Abraham Efficiently decoding Reed-Muller codes from random errors
  8. Ankit Yadav Derandomized Squaring of graphs
  9. Nada Improved Bounds and Algorithms for Hypergraph Two-coloring
  10. Shiv Krishna Combinatorial limitations of average-radius list-decoding


List of Topics Here are the ground rules. Topics will be allocated in a first cum first serve basis starting 21 Mar 10 am. (Mails sent before the start time will not be considered.) The process will be completed by Mar 22 5pm and final list will be announced on 24th Mar. The presentations (45 mins per person) will start from first week of April and will be scheduled in extra slots
  1. Exctractor Codes
  2. Quadratic Lower bound for 3 querry LDCs
  3. Extractors for Low-Weight Affine Sources
  4. Combinatorial limitations of average-radius list-decoding
  5. Linear-algebraic list decoding for variants of Reed-Solomon codes
  6. Efficiently decoding Reed-Muller codes from random errors
  7. Improved Bounds and Algorithms for Hypergraph Two-coloring
  8. Derandomized Squaring of graphs
  9. An elementary construction of constant-degree expanders
  10. The sum of d small-bias generators fools polynomials of degree d.
  11. Learning Random Monotone DNF
  12. Making Polynomials Robust to Noise
  13. Bounded Independence Fools Halfspaces
  14. Pseudorandom bits for polynomials
  15. A Chernoff Bound for Random Walks on Expander Graphs
  16. Short paths in expander graphs
  17. Cryptographic Hash Functions from Expander Graphs
Exams:
  • Mid Sem Mar 04, 9-11AM
  • End Sem Apr 24, 1-4 PM