CS-621 Theory Gems -- Fall 2012

Goal: The goal of this course is to present a bird's-eye view of some of the most exciting developments in theoretical computer science, as well as, discuss their context and connections to other fields. Our focus will be mostly on more recent - and thus not as widely known yet - topics.
This course is targeted at all mathematically-inclined students that are curious about theoretical computer science - even if they do not plan to do research in this area.

Prerequisites: Mathematical maturity and basic algorithmic background. Some experience with theoretical computer science beyond the introductory level (e.g., at the level of Advanced Algorithms) will be helpful, but it is not necessary.

Time and place: There will be two lectures per week - Wednesdays 15-17 in ~~BC 129~~ INM 203 and Thursdays 10-12 in BC 04.

Lecturer: Aleksander Mądry (aleksander.madry@epfl.ch), office hours: by appointment or Thursdays 14-15, INJ 113.

Grading: The grade will be based on 6-7 problem sets [50%], scribe notes (see below) [20%], and a final project that will consist of exploring a topic of interest related to this course [30%]. Class participation (e.g., interaction during the lecture, asking good questions) can also (positively) influence your grade.

Collaboration: Both the final project and scribing can (and probably should) be done in teams of two people. In case of problem sets, collaboration with one other person is also allowed, but: (1) the writeup of all the solutions has to be prepared independently (in particular, you should understand and be able to explain everything that is written in your solution); (2) in your writeup, you should include the name of your collaborator.

Scribe notes: For each lecture, there will be one team (of one or two students) in charge of taking detailed notes, typing them in LaTeX, preparing any needed figures, and sending them to the lecturer within at most 72 hours after the lecture. These notes will be posted on the course website.

LaTeX is a typesetting language in which most (if not all) scientific literature is written. So, if you are not familiar with it yet, it is probably a good time to do it now.
To start, take a look at www.latex-project.org and play with our template. (Make sure you have a distribution installed and don't forget to put the preamble.tex and fullpage.sty files in the same directory as the template.)

When preparing scribe notes, please use this template -- just edit it to include your notes. (The template requires preamble.tex and fullpage.sty files to compile. Put them in the same directory.) Here are some guidelines regarding the style of the notes.

The target audience of these notes is you -- students -- a couple of weeks after the lecture, when you already have forgotten what it was about. Therefore, while scribing the notes, you should strive to present, in succinct, readable, and technically correct (but not too formal) way, all the important points and results of the lecture. A couple of more concrete suggestions:

Start by briefly summarizing the main topics discussed in the lecture;
Try to use full sentences/prose - avoid bullet points;
(Very important) Make sure to also include the motivation, illustrative examples and intuitions related to the presented concepts/algorithms/proofs -- either the ones presented in the lecture or (even better!) the ones you came up on your own;
If there is a simple figure that you feel would be helpful in understanding something, try to include it too;
Make sure that all the formal arguments are correct and do not have any gaps in reasoning - if something in the argument is unclear to you, just email the lecturer for clarification.
Polish the language and spell check your notes before sending them to the lecturer;

(Here is a collection of decent scribe notes (from a different course) that can serve as an example of the expected style and quality.)

Problem sets: All solutions should be emailed to the lecturer as a PDF (typeset in LaTeX, not scanned, except for figures) -- for your convenience, there will be a template accompanying each problem set. Here are some additional guidelines.

You can use any source at your disposal (i.e., Google is your friend), but you have to acknowledge everything that you use;
You do not need to reprove anything that was shown in the class - just point to the relevant claim in the lecture notes;
Please be precise and (reasonably) formal.
Keep in mind that most of the problems ask you to provide a proof of a statement (as opposed to, say, just providing an example). Therefore, make sure that your reasoning is correct and there are no holes in it. (Be especially careful in that regard when proving "impossibility" results - check twice if you are not using any implicit assumptions in your reasoning.);
Please be concise. All the problems have solutions whose all details should comfortably fit on one page. If yours does not, you most likely are overlooking some simplification;

Problem Set 1. Due: October 14, 2012. Answer template.
Problem Set 2. Due: ~~October 28, 2012~~ November 4, 2012. Answer template.
Problem Set 3. Due: ~~November 18, 2012.~~ November 25, 2012. Answer template.
Problem Set 4. Due: December 21, 2012. Answer template.
Problem Set 5 (optional). Due: January 21, 2013. Answer template.

Mailing list: There is a mailing list for this course. To subscribe, send your name and SCIPER number to the lecturer.

Schedule:

Wednesday, September 19, 2012: How to get rich (if you have good advice). Learning-from-expert-advice framework; Multiplicative weights update method; Regret minimization; Notes. Further reading: Survey of MWU method and its applications.
Thursday, September 20, 2012: How computers learn. PAC model; Perceptron; Notes. Further reading: Machine Learning class by Avrim Blum, one by Nina Balcan and one by Rob Schapire - they also contain further references. Also, see an (advanced) EPFL course by Volkan Cevher (runs this semester!)
Wednesday, September 26, 2012: How computers learn (continued). Winnow algorithm; Support Vector Machines; Notes.
Thursday, September 27, 2012: How computers learn (continued). the Kernel Trick; Boosting; Notes.
Wednesday, October 3, 2012: How to play games. Intro to Game Theory, Nash equilibria, Braess' paradox; Notes. Further reading: Book on Algorithmic Game Theory (quite good introduction to the field, covers many topics, freely accessible).
Thursday, October 4, 2012: How to play games (continued). Zero-sum games, MinMax theorem, Existence and complexity of finding Nash equilibria; Notes.
Wednesday, October 10, 2012: How to play games (continued). Congestion games, Price of anarchy, Price of stability; Notes.
Thursday, October 11, 2012: How to play games (continued). Mechanism Design and Social Choice, Revelation principle, Gibbard-Satterthwaite theorem, Vickrey auction, VCG mechanism; Notes.
Wednesday, October 17, 2012: How to walk on graphs. Random walks; Notes. Further reading: a survey on random walks by László Lovász and a note on PageRank by Brian White. Also, a paper on PageRank axioms.
Thursday, October 18, 2012: Enter the Matrix. PageRank, Graph Laplacians, Courant-Fisher theorem; Notes. Further reading: Spectral Graph Theory course notes by Dan Spielman and (first part of) An Algorithmist's Toolkit course by Jon Kelner. Another great resource is a very recent monograph by Nisheeth Vishnoi.
Wednesday, October 24, 2012: Fun with eigenvalues. Graph Inequalities, Obstructions to mixing of random walks; Notes.
Thursday, October 25, 2012: Eigenvalues and cuts. Cheeger's Inequality, Diameter and eigenvalues;
Wednesday, October 31, 2012: Eigenvalues and random walks. More on graph inequalities, Discrete properties of random walks (hitting, commute, and cover time), cover time vs. diameter/spectral gap;
Thursday, November 1, 2012: Lecture cancelled;
Wednesday, November 7, 2012: Electrical flows and random walks. Electrical flows, Cover time and effective resistance, Random spanning trees; Further reading: An in-depth treatment of connections between electrical flows and random walks/spanning trees can be found in Chapters 2 and 4 of the book by Russell Lyons with Yuval Peres. Also, the monograph by Nisheeth Vishnoi provides (among other things) a remarkable exposition of nearly-linear time Laplacian system solver.
Thursday, November 8, 2012: Electrical flows and random walks (continued). Wrap up; Too much input, too little space - how to deal with big data. Streaming model, Counting distinct elements; Further reading: Sketching, Streaming and Sub-linear Space Algorithms course notes by Piotr Indyk.
Wednesday, November 14, 2012: Too much input, too little space - how to deal with big data (continued). Distinct elements problem; Notes.
Thursday, November 15, 2012: Too much input, too little space - how to deal with big data (continued). k-wise independent hash functions, L_2-norm estimation; Notes.
Tuesday, November 20, 2012: Too much input, too little space - how to deal with big data (continued). Frequent elements problem, Count-Sketch, Count-Min; Notes.
Wednesday, November 21, 2012: Too much input, too little space - how to deal with big data (continued). Sparse approximation problem, Compressed sensing, Lowerbounds for streaming algorithms; Notes.
Thursday, November 22, 2012: Too much input, too little space - how to deal with big data (continued). Communication-complexity-based lowerbounds for streaming algorithms;
Wednesday, November 28, 2012: How to project your data. Johnson-Lindenstrauss lemma; Notes. Further reading: Full proof can be found, e.g., in these notes (the "second" proof on page 3 is quite elementary and self-contained).
Thursday, November 29, 2012: How to keep your secrets. Intro to modern cryptography, one-time pad, one-way functions; Further reading: This (and the subsequent) lecture is roughly based on this chapter of an (excellent) book by Arora and Barak.
Wednesday, December 12, 2012: (Pseudo)randomness and security. Pseudorandom generators, Private-key encryption scheme via pseudorandom generators;
Thursday, December 13, 2012: How to prove something. Interactive proofs, IP=PSPACE, PCP theorem, Zero-knowledge proofs;
Wednesday, December 19, 2012: Computing blindfolded. Introduction to homomorphic encryption, zero-knowledge proofs via homomorphic encryption; Further reading: See here an excellent blog post on this topic.
Thursday, December 20, 2012: Computing blindfolded (continued). Construction of a homomorphic encryption scheme; Further reading: The construction we presented was developed here.