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 normalsized 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 wellprepared.
 Past courses along similar lines: A Theorist's toolkit
 Terry Tao's advice to budding
math researchers.
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 3747. AlonSpencer 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 lowrank
approximations. Eigenvalues of random matrices and semicircle law. 
Spectral
Algorithms by KannanVempala.Chapter 3.1 FurediKomlos paper on eigenvalues of random matrices. 
KannanVempala 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. 
AroraKale
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 AroraBarak and in O'donnell's lecture 17.
O'donnell's paper is here. 
HOMEWORK