Activities
Problem Sets :
 Problem Set1 Due date 11FEB2013.
 Problem Set2 Due date 25FEB2013.
 Problem Set3 Due date 01APR2013.
 Problem Set4 Due date 22APR2013.
 Problem Set5 Due date 29APR2013.( 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 15MAR2013.
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 firstcomefirstserve principle. You can send your preferences (at least two, by email or informing me in person) on or after 23032013 10AM and until 25032013 5PM. Please note that all mails sent before 23032013 10AM will be ignored. (This is to ensure that everyone gets to see the list before the starttime, assuming everyone checks emails at least once in two days.) For those who fail to send their preference by 25032013 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
SymmetryBreaking By Sriram Pemmaraju and Aravind Srinivasan
Tejas Kulkarni

The sum of d smallbias 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 Readk 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 ChernoffHoeffding 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 readonce formulas
Andrej Bogdanov Periklis Papakonstantinou Andrew Wan.
Akshay Degwekar

Active Property Testing
Sharath Chander

Chinese Remaindering with errors
Vamsi Krishna

BPSpace(S) subseteq DSPACE(S^3/2) by Michael Saks and Shiyu Zhou
Anant Dhayal