Algorithms Reading Group — MIT — CSAIL — THEORY


  • We ask all participants to read the instructions and policies (at the bottom of this page) at least once
  • For the moment we are aiming to hold the meetings on Fridays at 4pm in 32-G575. Expect the meetings to run for about 1 hour


Reading group email:
Reading group mailing list:
Alexandr Andoni
Petar Maymounkov
Anastasios (Tasos) Sidiropoulos


Cryptography & Complexity Reading Group


5/9/2008 — (Friday) — 4pm — 32·G575
Improved algorithmic versions of the Lovasz Local Lemma, Srinivasan, SODA'08
Presenter: Jacob Scott
5/2/2008 — (Friday) — 4pm — 32·G575
Presenter: Krzysztof Onak
4/25/2008 — Cancelled


4/18/2008 — (Friday) — 4pm — 32·G575
Priority sampling for estimation of arbitrary subset sums, Duffield, Lund, Thorup, J.ACM'07
Presenter: Mihai Patrascu
4/4/2008 — (Friday) — 4pm — 32·G575
Graph Sparsification by Effective Resistances, Spielman, Srivastava, STOC'08
Presenter: Aleksander Madry
2/29/2008 — (Friday) — 4pm — 32·G575
On Agnostic Boosting and Parity Learning, Kalai, Mansour, Verbin, STOC'08
Presenter: Alexandr Andoni, Notes
2/22/2008 &mdash (Friday) — 4pm — 32·G575
Graph partitioning using single commodity flows, Vazirani, Khandekar, Rao, STOC'06
Presenter: Petar Maymounkov, Notes

Suggested papers

Cuts and partitioning

Sparse approximation and sketching


Areas of interest and intention

We would like to maintain focus on the topic of papers presented. We expect that each new paper suggestion will fit in a broad area of interest as well as one or more narrow areas of interest.
  • Broad areas
    • Approximation algorithms in optimization
    • Sparse approximation algorithms (in streaming, sensing and sketching)
    • Data structures (classical and streaming)
    • Sub-linear time algorithms
  • Narrow areas and techniques
    • Metric embeddings
    • Matrix analysis – e.g. decompositions, approximate arithmetic, least squares, norm inequalities
    • Functional Analysis and Convex Geometry &ndash e.g. embeddings of Banach spaces, operators (coherence, width, RIP)
    • Fast Fourier Transforms – e.g. fast algorithms, combinatorial interpretation of functional operators
    • Explicit constructions
    • Spectral techniques – e.g. cutting, clustering, parallelization, routing
    • Communication complexity – e.g. number-on-forehead model
    • Algorithmic Topology
    • Additive Combinatorics – e.g. anti-concentration theorems, harmonic analysis of combinatorial objects
    • Privacy – e.g. from the point of view of geometry and functional analysis
    • LP/SDP – e.g. hierarchies, rounding, combinatorial methods, integrality gaps

Instructions for presenters and attenders

We would like to make sure that the group meetings are effective and engaging for both presenters and attenders. This is why:
We ask presenters to prepare a page or two (more is OK) of notes, containing
  1. A description of the paper's relation to prior work, and
  2. Statements of the main results and the more important technical tools. These must be written in a correct and formal manner (not necessarily in full generality). The idea is to enable people to perform back-of-the-envelope calculations without refering to the original paper.
  3. When manageable, proofs of key lemmas are encouraged and/or proofs of steps that are omitted from the paper
  4. Send us (by email) the PDF of your notes, so we can put them up on the page

Overall, the goal is to have the notes tell a complete story, very much like scribe notes for lectures do.

If you want to save yourself time in writing these notes (while writing them well), take a look at Terry Tao's advice on writing a rapid prototype (and in fact take a look at all his articles and links about writing — they are good).

The notes need not be typeset in LaTeX. It would be perfectly OK if they are handwritten and scanned into PDF. (This can be done on 5th and 9th floors of Stata.) We intend to keep an archive of all notes on this site!

We ask attenders to read and think about the papers before the meetings. We hope that this way discussions can be more productive, hopefully leading to new discoveries
The idea is that attenders will read and get a good grasp of the papers (without investing an exorbitant amount of time), while identifying the steps that they can't verify. The presenters (who would spend much more time with the papers) should thus be ready to fill in all gaps, so that at the end everyone can walk away with full understanding.

Policy, emphasis and advice

  • In order to keep everybody engaged and on equal ground, presenters are not to present their own results
  • Typically, papers will fall in one or two categories:
    1. Open problems paper: This would usually be a paper that either (a) initiates a new (well motivated) study and concludes with a hard open problem, or (b) a paper that makes a partial step towards an old open problem. In such cases, we encourage the presenters to tell us:
      1. What is the "grand goal",
      2. Why, and
      3. What needs to be done next to get closer
    2. Techniques paper: A paper that makes partial progress towards a well-known open problem usually does so by introducing novel techniques. When presenting such papers, we hope that you try to:
      1. Give us a good explanation why prior techniques fail,
      2. Investigate what other areas (in your expertise) these new techniques could apply to
  • The organizers will do their best to schedule talks in a topic-consistent manner. In other words, we will try to have consequtive talks be on related topics and in the proper order if there are inter-dependencies (among the papers) or a natural build-up of techniques
All being said, it is hard to meet all requests (above), so use them as guidelines more so than rules. Thanks!