Problem SetsWe plan to have 5 problem sets.
- List of topics are as follows. This will be available in a first-come-first-serve basis. Please communicate your choices by 22-03-2016.
- The choice/assignment of topics will be announced on 23 Mar.
- Presentations will start from third week of Apr.
List of topics
- PP is closed under intersection.
Is the Valiant-Vazirani Isolation Lemma Improvable?
Bipartite Perfect Matching is in quasi-NC
2 + epsilon SAT is NP hard. Zero Knowledge and Circuit Minimization.
- Interactive PCP ( Can be taken up by two people ).
- On the Unique Games Conjecture and application to hardness of approximation ( Can also be taken up by two people)
- Arthur Merlin Games in Linear Decision Trees.
Undirected Connectivity in Deterministic Log Space Amplifying lower bounds by means of self reducibility.
- On derandomizing algorithms that err extremley rarely
- New algorithms and lower bounds for circuits with linear threshold gates
- Certifying Polynomials for AC0[Parity] circuits, with applications.
On Improved Degree Lower Bounds for Polynomial Approximation
- Approximating AC0 by Small Height Decision Trees and a Deterministic Algorithm for#AC0 SAT
|Shijin R||AM with multiple Merlins.||20 Apr|
|Vijayaraghunathan||Is the Valiant-Vazirani Isolation Lemma Improvable?||20 Apr|
|Subhadra Nanda||2 + epsilon SAT is NP hard.||23 Apr|
|Shiva Krishna||Interactive PCPs.||23 Apr|
|Santhosjhini||Interactive PCPs.||23 Apr|
|Sundar A||Bipartite Perfect Matching is in quasi-NC.||23 Apr|
|Kavin Kumar||Undirected Connectivity in Deterministic Log Space.||23 Apr|
ExaminationThere will be a mid-semester and an end semester examination.
Mid semester exam : 12 Mar, 2016
End semester exam : 10:00 - 13:00 02 May, 2016