Activities

Problem Sets

We plan to have 5 problem sets, and the best 4 will be considered for evaluation. The tentative schedule is as follows:

• Probelem set 1: Jan 26 (delayed) sent on Jan 29,    Due on Feb 13 (extended to Feb 16).
• Probelem set 2: Feb 15, (Delayed)    Due on Mar 4
• Probelem set 3: Mar 11,   Due on Mar 24
• Probelem set 4: Mar 21,    Due on Apr 09
• Probelem set 5: Apr 10,   Due on Apr 28




Project Presentations

• List of topics are as follows. This will be available in a first-come-first-serve basis. Please communicate your choices by 17-02-2014.
• The choice/assignment of topics will be announced by the first week of Mar. ( Done , please see below.)
• Presentations will start from first week of Apr.
<

List of topics

1. PP is closed under intersection.
2. Amplifying lower bounds by means of self reducibility.
3. Is Valiant Vazirani Lemma Improvable?
4. On derandomizing algorithms that err extremley rarely
5. New algorithms and lower bounds for circuits with linear threshold gates
6. Arthur Merlin Games in Linear Decision Trees.
7. Certifying Polynomials for AC0[Parity] circuits, with applications.
8. AM with multiple Merlins
9. Approximating AC0 by Small Height Decision Trees and a Deterministic Algorithm for #AC0-SAT




Choice of Topics

Ankit Chauhan	Parameterized Complexity of Counting.
Assim Ambadi	On the Hardness of Graph Isomorphism
Devakar Verma	Tight Bounds for Monotone Switching Networks via Fourier Analysis.
Kartik Gupta	Unique games conjecture and hardness of approximation for optimization problems.
Preethi L	Approximating AC0 by small height decision trees & a deterministic algorithm for #AC0 SAT.
Ramya C	Hardness-randomness tradeoff for bounded depth arithmetic circuits.
Saurabh Sawlani	Making non-determinism unambiguous.
Subin K	Certifying Polynomials for AC0[Parity] circuits, with applications.





Examination

We will have an end semester examination and a viva-voice.
End semester exam : 01-05-2014, 8:30-10:00
Viva : 01-05-2014, 10:30 onwards