Activities
This page will list down the course activities in addition to the lectures.
Problem Sets :
- Problem Set 1, Jan 31, Deadline: Feb 14
- Problem Set 2, Feb 14, Deadline: Feb 28
- Problem Set 3, Mar 12, Deadline: Mar 24
- Problem Set 4, Mar 30, Deadline: Apr 15
- Problem Set 5, Apr 09, Deadline: Apr 25
Presentation: Here are the ground rules.
Topics announced by 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 2 and 3 for which the portions are not completely covered before the deadline for choosing topics. This can be done on the "Instructor Office hours" of the course. The presentations (45 mins per person) will start from first week of April and will be scheduled in extra slots.
Topics for Presentations - from Theme 1 - Probablistic Method & Applications
- A constructive proof of the general Lovasz Local Lemma [1]
- On Allocations that Maximize Fairness [1]
- New Constructive Aspects of the Lovász Local Lemma [2]
- Improved bounds and algorithms for hypergraph two-coloring [1]
- Testing Hypergraph Coloring [1]
Topics for Presentations - from Theme 2 - Coding Theory & Applications.
- Complexity of Computational Problems in Coding Theory - See here and here [1]
- 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]
- Secret Sharing Schemes and Error Correcting Codes [1].
- Trevisan Extractor & Extractor Codes [2]
Topics for Presentations - from Theme 3 - Fourier Analysis & Applications.
- Learning and Lower Bounds for AC^0 with Threshold Gates [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]
Exams:
- Exam - 1 Mar 22, Saturday 10am - 12:30pm.
- Exam - 2 May 03, Saturday 2pm - 5pm