Manoj Gopalkrishnan

Fall 2009: Graduate Seminar in Algorithms and Complexity

Update on 11 August, 2009: The list of papers with presenters 

Where: STCS seminar room, TIFR Mumbai.

When: Tuesdays and Thursdays, 2 pm to 3:30 pm.

Course objective: To explore some current topics from algorithms and computational complexity theory.

Course structure: This will be a seminar-style course. Students will be expected to read all the assigned papers, make class presentations when called upon to do so, and participate in class discussions. Grades will be based on presentations and class participation. There will be no exams.

Prerequisites: Mathematical maturity, and familiarity with graduate-level algorithms and complexity theory will be assumed.

Syllabus: What we end up covering will depend on the interests of the class, and how much time is available. However, here is a tentative list.

1. "The complexity of computing a Nash equilibrium", Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou, Communications of the ACM Volume 52, Number 2 (2009), Pages 89-97. (Also see SIAM J. Comput version, vol 39, pp 195-259).

2. "Approximate counting, uniform generation and rapidly mixing Markov chains", Mark Jerrum and Alistair Sinclair, Information and Computation  82 (1989), 93-133.

3. "Approximating the permanent," Mark Jerrum and Alistair Sinclair, SIAM Journal on Computing  18 (1989), 1149-1178.

4. "A constructive proof of the Lovasz local lemma," Robin Moser, Proceedings of the 41st annual ACM symposium on Theory of computing, Bethesda, MD, USA, pp. 343-350, 2009.

5. "A New Approach to Auctions and Resilient Mechanism Design," Jing Chen, Silvio Micali.

6. "The topological structure of asynchronous computability," Maurice Herlihy, Nir Shavit, Journal of the ACM, Vol. 46, No. 6, November 1999, pp. 858 –923.

7. "The Geometry of Binary Search Trees," Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu.

8. "Designing Compressive Sensing DNA Microarrays,"  Wei Dai, Mona A. Sheikh, Olgica Milenkovic, and Richard G. Baraniuk.

9. "Quadratic dynamical systems," Rabinovich, Sinclair, Wigderson, Proc. 33rd IEEE Symp. Found. Comput. Science, 1992, 304 - 313.

10. "Holographic Algorithms," Leslie Valiant, SIAM J. COMPUT., 2008, Vol. 37, No. 5, pp. 1565–1594.

11. "Factoring large numbers with the TWIRL device," Adi Shamir and Eran Tromer, Lecture Notes in Computer Science, Advances in Cryptology - CRYPTO 2003.

12. "PRIMES is in P," Manindra Agarwal, Neeraj Kayal and Nitin Saxena.

13. "On the Complexity of Envy-Free Cake Cutting," Xiaotie Deng, Qi Qi, Amin Saberi.

Presentation guidelines

1. The focus will be on the content and not on the form of the presentation. However, take a look at http://www.cs.berkeley.edu/~jrs/speaking.html to avoid some common mistakes.
2. There is a lot of material in some of these papers. Do NOT try to be comprehensive. Instead, focus on communicating one key idea effectively.
3. Motivate the question you are trying to answer. Why is it important? Why is it the right question? What is its history?
4. Solve an example where the question is trivial, to help fix what the question is all about.
5. State the question in a precise and accessible manner, after introducing the concepts necessary to do so.
6. Give an example where the solution to the question is not obvious.
7. Show us how the ideas in the paper work out for this one example.
8. You will be frequently interrupted. You should have a thorough understanding of the material, so that you are able to think on your feet and defend the argument you are presenting when challenged. Expect to be asked to demonstrate the methods you are presenting on specific examples during your presentation.
9. Even if it is not your turn to present, read the paper. Your ability to ask probing questions and contribute in other ways in class will count towards your grade, and more importantly, help you learn.
10. Many of the papers we plan to cover have both conference and journal versions. Some even have Wikipedia articles on them. It may be a good idea to first read the popular science accounts, and then the conference version, and then the journal version. This way you get a grip on the big picture, and avoid getting lost in the details.