
Announcements
 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 32G575.
Expect the meetings to run for about 1 hour


Contacts
 Reading group email:
 Reading group mailing list:
 — Selfservice
 Organizers:
 Alexandr Andoni
 Petar Maymounkov
 Anastasios (Tasos) Sidiropoulos
Links
 Cryptography & Complexity Reading Group

Upcoming
 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
 TBA
Presenter: Krzysztof Onak
 4/25/2008 — Cancelled
Archives
 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
 On Partitioning Graphs via Single Commodity Flows,
Orecchia, Schulman, U. Vazirani, Vishnoi, STOC'08
 $O(\sqrt{\log n})$ approximation to sparsest cut in $\tilde{O}(n^2)$ time, Arora, Hazan, Kale, FOCS'04
 Clustering for Metric and NonMetric distance measures, Ackermann,
Blomer, Sohler, SODA'08
Sparse approximation and sketching
 Fast
Dimension Reduction Using Rademacher Series on Dual BCH Codes, Ailon, Liberty, SODA'08
 Improved Approximation Algorithms for Large Matrices via Random
Projections, Sarlos, FOCS'06 (Claimed by Petar Maymounkov)
 Sampling
from large matrices: an approach through geometric functional analysis, Rudelson, Vershynin, JACM'07
 The LittlewoodOfford Problem and Invertibility of Random Matrices,
Rudelson, Vershynin (Claimed by Petar Maymounkov)
Unsorted
 Fast Integer Multiplication, Furer, STOC'07
 Sphere recognition lies in NP, Schleimer, '08
 MultiArmed Bandits on Metric Spaces, Kleinberg, Slivkins, Upfal, STOC'08
 Smooth sensitivity and sampling in private data analysis,
Nissim, Raskhodnikova, Smith, STOC'07
 Unique Games on Expanding Constraint Graphs are Easy, Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur
Tulsiani and Nisheeth Vishnoi, STOC'08 (To appear)
 The unique games conjecture, integrality gap for cut problems and
embeddability of negative type metrics into L1, Khot, Vishnoi, FOCS'05

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)
 Sublinear 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. numberonforehead model
 Algorithmic Topology
 Additive Combinatorics – e.g. anticoncentration 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
 A description of the paper's relation to prior work, and
 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
backoftheenvelope calculations without refering to the original paper.
 When manageable, proofs of key lemmas are encouraged and/or proofs
of steps that are omitted from the paper
 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:
 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:
 What is the "grand goal",
 Why, and
 What needs to be done next to get closer
 Techniques paper: A paper that makes partial progress towards a
wellknown open problem usually does so by introducing novel techniques. When presenting
such papers, we hope that you try to:
 Give us a good explanation why prior techniques fail,
 Investigate what other areas (in your expertise) these new techniques could apply to
 The organizers will do their best to schedule talks in a topicconsistent manner. In other
words, we will try to have consequtive talks be on related topics and in the proper order
if there are interdependencies (among the papers) or a natural buildup of techniques
All being said, it is hard to meet all requests (above), so use them as
guidelines more so than rules. Thanks!
