Activities
This page will list down the course activities in addition to the lectures.Problem Sets (40%):
- Problem Set 1 : Feb 6, Deadline: Feb 16
- Problem Set 2 : Feb 24, Deadline: Mar 10
- Problem Set 3 : Apr 1, Deadline: Apr 15
- Problem Set 4 : Apr 15, Deadline: Apr 27
- Exam 1 (20%) : Mar 21, Saturday 8am - 10am.
- Exam 2 (20%) : May 2, 4pm - May 3, 4pm (take-home)
Course Project & Presentation (20%):
Here are the ground rules. Topics will be announced on Mar 10th and the choice/assignment of topics will be announced by Mar 17th. Each paper comes with a "bucket size" which indicates the number of students who can take up the project together (as a group). See this number within []. The students are encouraged to meet the instructors in person before choosing a topic - especially for Theme 3 and 4 for which the portions are not completely covered before the deadline for choosing topics. The presentations (45 mins per person) will start from first week of April and will be scheduled in extra slots.
Theme: Probablistic Method & Applications
- On Allocations that Maximize Fairness [1]
- A constructive proof of the general Lovasz Local Lemma [1]
- New Constructive Aspects of the Lovasz Local Lemma [2]
- Constructive Discrepancy Minimization by Walking on The Edges [1]
- Constructive Algorithms for Discrepancy Minimization [2]
- Constructive discrepancy minimization for convex sets [2]
- Improved bounds and algorithms for hypergraph two-coloring [1]
- The complexity of distributions ([1] if presenting results (1) and (2) from the abstract; [2]2 if presenting all 4 results mentioned in the abstract)
- The Randomized Communication Complexity of Set Disjointness [1]
- Simple Analysis of Graph Tests for Linearity and PCP [1]
Theme : Coding Theory & Applications.
- Complexity of Computational Problems in Coding Theory - See here and here [1]
- Guruswami-Sudan Algorithm, improvements, & Folded Reed-Solomon Codes [2]
- Matrix Product and Codes - See here and here. [2]
- Coding and Decoding of Concatenated Codes - See here and here [1]
- Expander Codes and their applications - See here and here [1]
- Identity Testing of Depth-3 circuits and LDCs [1]
- Multiplicity Codes and Matching Vector Codes [2]
- Secret Sharing Schemes and Error Correcting Codes [1].
- Extractor Codes [1]
- Lower Bounds for 3-query Linear LDCs [1]
- Lower Bounds for Approximate LDCs [1]
Theme: Pseudo-randomness, Fourier Analysis & Applications.
- Almost k-wise independent sample space constructions and lower bounds [1]
- Construction of min-wise independent permutation families [1]
- Pseudorandom bits for polynomials [1].
- Learning random monotone DNF [1]
- Making Polynomials Robust to Noise [1]
- Testing Properties of Linear Functions [1]
- The sum of d small-bias generators fools polynomials of degree d [1]
- Extensions to Method of Multiplicities & Applications.[2]
- Bounded Independence Fools Halfspaces [1]
- A Simple Proof of Bazzi's Theorem [1]
- Polylogarithmic Independence Fools Constant Depth Polysize circuits [1]