"Best Papers" Reading Group Winter 2015

This is a combined faculty-student reading group.

Date Paper Speaker
1/16 Independence Numbers of Locally Sparse Graphs and a Ramsey Type Problem by Alon Vincent
1/23 Approximating independent sets in sparse graphs by Bansal Alireza
1/30 Composable and efficient mechanisms by Syrgkanis and Tardos Kira
2/6 How to Compress Interactive Communication by Barak, Braverman, Chen, Rao Siva
2/13 Exponential Separation of Information and Communication - Ganor, Kol, Raz Makrand
2/20 Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees by Marcus, Spielman, Srivastava Cyrus + Mert
2/17 A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time by Kelner, Orecchia, Sidford, Zhu Jeffrey
3/6 A Note on Cut-Approximators and Approximating Undirected Max Flows by Richard Peng Xin

The following papers were also suggested as "best papers" from the last ~10 years to read:
  1. Linear Codes cannot Approximate the Network Capacity to within a Constant Factor by Lovett
  2. Sign Rank, VC Dimension and Spectral Gap by Alon, Moran, Yehudayoff
  3. The Cell Probe Complexity of Dynamic Range Counting by Larsen
  4. A simple and approximately optimal mechanism for an additive buyer by Babaioff, Immorlica, Lucier, Weinberg
  5. An n-to-1 bidder reduction for multi-item auctions and its applications by Yao
  6. Understanding incentives: mechanism design becomes algorithm design by Cai, Daskalakis, Weinberg; see also Weinberg 2014
  7. Barriers to near-optimal equilibria by Roughgarden
  8. Incentivizing exploration by Frazier, Kempe, Kleinberg, Kleinberg
  9. A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations by Miccianco, Voulgaris
  10. Graph Sparsification by Effective Resistances by Spielman and Srivastava
    [Added related paper: "Linear-Sized Spectral Sparsification in Almost Quadratic Time and Regret Minimization Beyond Matrix Multiplicative Weight Updates" by Orecchia and Zhu. This shows how to view Spielman-Srivastava in the "multiplicative weights" framework.]
  11. Constructive Discrepancy Minimization by Walking on The Edges by Meka and Lovett
  12. A Simple O(loglog(rank))-Competitive Algorithm for the Matroid Secretary Problem by Feldman, Svensson, Zenklusen
  13. Friedgut's theorem via the log-Sob inequality (from Cuts in Cartesian Products of Graphs by Sachdeva and Tulsiani)
  14. Commuting time geometry of ergodic Markov chains by Doyle and Steiner