Activities

Problem Sets

We plan to have 5 problem sets.

Project Presentations

• 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

1. PP is closed under intersection.
2. Is the Valiant-Vazirani Isolation Lemma Improvable?
3. Bipartite Perfect Matching is in quasi-NC
4. 2 + epsilon SAT is NP hard.
5. Zero Knowledge and Circuit Minimization.
6. Interactive PCP ( Can be taken up by two people ).
7. On the Unique Games Conjecture and application to hardness of approximation ( Can also be taken up by two people)
8. Arthur Merlin Games in Linear Decision Trees.
9. Undirected Connectivity in Deterministic Log Space
10. Amplifying lower bounds by means of self reducibility.
11. On derandomizing algorithms that err extremley rarely
12. New algorithms and lower bounds for circuits with linear threshold gates
13. Certifying Polynomials for AC0[Parity] circuits, with applications.
14. On Improved Degree Lower Bounds for Polynomial Approximation
15. Approximating AC0 by Small Height Decision Trees and a Deterministic Algorithm for#AC0 SAT



Schedule.

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





Examination

There 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