Problem Sets :

Collaboration Policy
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
1st day 10%
2nd day 10%
3rd day 15%
4th day 20%
5th day 20%
6th day Submissions are NOT allowed

Midsem Exam :


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
  1. Learning and Lower Bounds for AC0 with Threshold Gates- Parikshit Gopalan and Rocco Servedio
    Ankit Chauhan
  2. The Randomized Coloring Procedure with Symmetry-Breaking By Sriram Pemmaraju and Aravind Srinivasan
    Tejas Kulkarni
  3. The sum of d small-bias generators fools polynomials of degree d By Emanuele Viola
    Gaurav Singh
  4. A Constructive Proof of the General Lovasz Local Lemma By ROBIN A. MOSER and GABOR TARDOS
    Sumathi + Anand Aiyer
  5. Rumor spreading in social networks By Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi
    William moses Jr.
  6. A Tail Bound for Read-k Families of Functions By Dmitry Gavinsky, Shachar Lovett, Michael Saks and Srikanth Srinivasan
    Vishal Pandya
  7. (Probabilistic) Recurrence Relations Revisited by Shiva Chaudhuri and Devdatt Dubhashi
    Choppa Aditya
  8. Randomized algorithms for DNF Counting
    Section 11.2 in Randomized Algorithms by Motwani and Raghavan.
    Anant Nag
  9. Min Cut
    Section 10.2 in the book Randomized Algorithms by Motwani and Raghavan.
    Saurabh Kumar Verma
  10. Private Information Retrieval
    Section 7.1 of the Survey by Sergei Yekhanin.
    Suraj Sangavkar
  11. 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
  12. 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
  13. 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
  14. Pseudorandomness for read-once formulas Andrej Bogdanov Periklis Papakonstantinou Andrew Wan.
    Akshay Degwekar

  15. Active Property Testing
    Sharath Chander

  16. Chinese Remaindering with errors
    Vamsi Krishna

  17. BP-Space(S) subseteq DSPACE(S^3/2) by Michael Saks and Shiyu Zhou
    Anant Dhayal

End-semester Exam

End semester exam held on 04-05-2013, 2-4pm.