Schedule
 Useful Links
 Homework

About this course

  This course is primarily aimed at first and second year graduate students and seeks to get them started on research in theoretical CS.  It will give them the skills and confidence to approach  research problems. The course's title is borrowed from George Polya's classic advice book for math students. Undergrads are welcome in the course but should contact me first.

I will share research ideas I am working on and we can discuss some of yours. We will read recent papers, chosen either for the importance of the result itself, or for the tools they use. We will have guest lecturers talk about their working style and ongoing research. Over and over again we will see that doing research breaks down into the following components:

  • Familiarity with tools.  You have to know the basic mathematical and conceptuatl tools, and over the semester we will encounter quite a few of them.
  • Background reading on your topic. What is already known and how was it proven? Research involves figuring out how to stand on the shoulders of others (could be giants, midgets, or normal-sized people).
  • Ability to generate new ideas and spot the ones that dont work. I cannot stress the second part enough. The only way you generate new ideas is by shooting down the ones you already have.
  • Flashes of genius. Somewhat overrated; the other three points are more important. Insights come to the well-prepared.

Useful Links

  1. Past courses along similar lines: A Theorist's toolkit
  2. Terry Tao's advice to budding math researchers.

Lecture Schedule:

Thursdays 1:30-4:20, CS 401. (First meeting: Sept 17)

Lecture Number & Topic
 Essential reading
 Additional reading/work
1. Sept 17.
Concentration of Measure. Chernoff, Martingale, and Talagrand bounds. Applications
 Keith Ball: An elementary introduction to modern convex geometry, p 37--47.

Alon-Spencer chapter on concentration bounds
 Colin McDiarmid: Concentration.
2. Sept 24.
Finish Talagrand.
"On the complexity of financial derivatives."
Introduction to planted graph problems and spectral methods

 ABBG paper on derivatives.
Eigenvalue lecture in "Theorist's toolkit".
Alon Krivelevich Vu paper on concentration of eigenvalues.
 Deciphering the crash
by M. Brunnermeier
3. Oct 1. Solving planted graph problems (planted clique, planted bisection etc) via low-rank approximations. Eigenvalues of random matrices and semicircle law.


 Spectral Algorithms by Kannan-Vempala.Chapter 3.1
Furedi-Komlos paper on eigenvalues of random matrices.
 Kannan-Vempala section 3.3. for alternative proof of thm on eigenvalues of random matrices.

Paper by P. Deift on universality of semicircle laws.
4. Oct 8. Measure concentration in complexity. Yao's XOR lemma and Direct Product theorems.
 GNW survey on XOR lemma; the proof we did is Levin's.
Unger's article with his new proof of direct product theorems.
5. No lecture.

6. Oct 22. Guest lecture by Anup Rao. Direct sum theorems in communication complexity
 Paper by Barak et al.
7. Oct 29. Multiplicative update rule (basic and matrix version). Geometry, Flows, and Cuts.
MW Algorithms; survey by Arora, Hazan, Kale.
Geom., flow, cuts survey by ARV
8. Nov 12. Matrix MW rule.Finished geometry, flows, and cuts.
 Arora-Kale paper for Matrix MW rule.  Also applies  framework for finding expander flows.
 New proof of ARV theorem in Jonah Sherman's paper.
QIP=PSPACE paper is here
9. Nov 19. Guest lecturer: Moses Charikar. Intro to approximation algorithms & rounding.

10. Dec 3. Fourier transforms. Analysis of linearity test and dictatorship test. O'Donnell's hardness amplification for NP.
 O'Donnell's lecture 3 and lecture 18
 Impagliazzo's hard core lemma is explained both in Arora-Barak and in O'donnell's lecture 17. O'donnell's paper is here.





HOMEWORK

  1.  HW 1 due Sept 24 in class.
  2. HW2 due Oct 1 in class
  3. HW3 due Oct 8 in class.
  4. HW4: Read 3 papers in STOC/FOCS/JACM and write 1-pg summary of each. Due Oct 22.
  5. HW 5: Due Dec 3 in class.

Design brrowed from  FullAhead.