Problem Sets :
- Problem Set-1   Due date 11-FEB-2013.
- Problem Set-2   Due date 25-FEB-2013.
- Problem Set-3   Due date 01-APR-2013.
- Problem Set-4   Due date 22-APR-2013.
- Problem Set-5 Due date 29-APR-2013.( This problem set is optional. Best FOUR problem sets will be considered for final evaluation.)
Collaboration is allowed (without affecting the grades), but subject to the following conditions:
- The solutions should be written individually in one's own words. Mass copying is NOT permitted.
- Collaborations (if any) should be acknowledged.
- Solutions should be typeset in LaTeX and uploaded through moodle.
Penalty for late submission
|Delay||Reduction in grades|
|6th day||Submissions are NOT allowed|
Midsem Exam :
- Midsem exam was held on 15-MAR-2013.
PresentationHere is a list of papers. As indicated below, some of the papers can be presented jointly by two people.
Policy for topic allocation:
It will be based on first-come-first-serve principle. You can send your preferences (at least two, by email or informing me in person) on or after 23-03-2013 10AM and until 25-03-2013 5PM. Please note that all mails sent before 23-03-2013 10AM will be ignored. (This is to ensure that everyone gets to see the list before the start-time, assuming everyone checks emails at least once in two days.) For those who fail to send their preference by 25-03-2013 5PM, an arbitrary unassigned topic will be assigned. Once the paper assignment is done, each one of you (including those who have already chosen their topics) need to meet me twice: 1) Soon after the allocation to briefly discuss about pitching your presentation. 2) At least a day before your presentation, to discuss about your plans for the presentation.
List of Topics
Learning and Lower Bounds for AC0 with
Threshold Gates- Parikshit Gopalan and Rocco Servedio
The Randomized Coloring Procedure with
Symmetry-Breaking By Sriram Pemmaraju and Aravind Srinivasan
The sum of d small-bias generators fools polynomials of
degree d By
A Constructive Proof of the General Lovasz Local Lemma By
ROBIN A. MOSER and GABOR TARDOS
Sumathi + Anand Aiyer
Rumor spreading in social networks By
Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi
William moses Jr.
A Tail Bound for Read-k Families of Functions By
Dmitry Gavinsky, Shachar Lovett, Michael Saks and Srikanth Srinivasan
(Probabilistic) Recurrence Relations Revisited by
Shiva Chaudhuri and Devdatt Dubhashi
Randomized algorithms for DNF Counting
Section 11.2 in Randomized Algorithms by Motwani and Raghavan.
Section 10.2 in the book Randomized Algorithms by Motwani and Raghavan.
Saurabh Kumar Verma
Private Information Retrieval
Section 7.1 of the Survey by Sergei Yekhanin.
Method of Bounded Variances, Application to Dealing with unlikely circumstances
Section 8.2.3 in the Book Concentration of Measure for the analysis of Randomized Algorithms by Dubhashi and Panconesi.
Shiv Poojan Singh
Janson's inequality, applications to subgraph counts and Randomized Rounding
Section 3.3 in the Book Concentration of Measure for the analysis of Randomized Algorithms by Dubhashi and Panconesi.
Randomized Skip Lists: An application of Chernoff-Hoeffding bound.
Section 2.3 in the Book Concentration of Measure for the analysis of Randomized Algorithms by Dubhashi and Panconesi.
Ashwini Kumar Sahoo
Pseudorandomness for read-once formulas
Andrej Bogdanov Periklis Papakonstantinou Andrew Wan.
Active Property Testing
Chinese Remaindering with errors
BP-Space(S) subseteq DSPACE(S^3/2) by Michael Saks and Shiyu Zhou