Activities
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.
Submission
- Solutions should be typeset in LaTeX and uploaded through moodle.
Penalty for late submission
| Delay | Reduction in grades |
| 1st day | 10% |
| 2nd day | 10% |
| 3rd day | 15% |
| 4th day | 20% |
| 5th day | 20% |
| 6th day | Submissions are NOT allowed |
Midsem Exam :
- Midsem exam was held on 15-MAR-2013.
Presentation
Here 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
Ankit Chauhan
-
The Randomized Coloring Procedure with
Symmetry-Breaking By Sriram Pemmaraju and Aravind Srinivasan
Tejas Kulkarni
-
The sum of d small-bias generators fools polynomials of
degree d By
Emanuele Viola
Gaurav Singh
-
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
Vishal Pandya
-
(Probabilistic) Recurrence Relations Revisited by
Shiva Chaudhuri and Devdatt Dubhashi
Choppa Aditya
-
Randomized algorithms for DNF Counting
Section 11.2 in Randomized Algorithms by Motwani and Raghavan.
Anant Nag
-
Min Cut
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.
Suraj Sangavkar
-
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.
Ramnath J
-
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.
Akshay Degwekar
-
Active Property Testing
Sharath Chander
-
Chinese Remaindering with errors
Vamsi Krishna
-
BP-Space(S) subseteq DSPACE(S^3/2) by Michael Saks and Shiyu Zhou
Anant Dhayal