Problem SetsWe 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
- 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
- PP is closed under intersection.
- Amplifying lower bounds by means of self reducibility.
- Is Valiant Vazirani Lemma Improvable?
- On derandomizing algorithms that err extremley rarely
- New algorithms and lower bounds for circuits with linear threshold gates
- Arthur Merlin Games in Linear Decision Trees.
- Certifying Polynomials for AC0[Parity] circuits, with applications.
- AM with multiple Merlins
- 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.|
ExaminationWe 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