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

Contacts

Reading group email:

Reading group mailing list:

— Self-service

Organizers:

Alexandr Andoni

Petar Maymounkov

Anastasios (Tasos) Sidiropoulos

Links

Cryptography & Complexity Reading Group

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 Non-Metric 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 Littlewood-Offord 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
• Multi-Armed 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

• 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 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

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