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: (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.

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