"Best Papers" Reading Group Winter 2015
This is a combined facultystudent 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 NearlyLinear Time by Kelner, Orecchia, Sidford, Zhu  Jeffrey 
3/6  A Note on CutApproximators 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:
 Linear Codes cannot Approximate the Network Capacity to within a Constant Factor by Lovett
 Sign Rank, VC Dimension and Spectral Gap by Alon, Moran, Yehudayoff
 The Cell Probe Complexity of Dynamic Range Counting by Larsen
 A simple and approximately optimal mechanism for an additive buyer by Babaioff, Immorlica, Lucier, Weinberg
 An nto1 bidder reduction for multiitem auctions and its applications by Yao
 Understanding incentives: mechanism design becomes algorithm design by Cai, Daskalakis, Weinberg; see also Weinberg 2014
 Barriers to nearoptimal equilibria by Roughgarden
 Incentivizing exploration by Frazier, Kempe, Kleinberg, Kleinberg
 A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations by Miccianco, Voulgaris

Graph Sparsification by Effective Resistances by Spielman and Srivastava
[Added related paper: "LinearSized Spectral Sparsification in Almost Quadratic Time and Regret Minimization Beyond Matrix Multiplicative Weight Updates" by Orecchia and Zhu. This shows how to view SpielmanSrivastava in the "multiplicative weights" framework.]  Constructive Discrepancy Minimization by Walking on The Edges by Meka and Lovett
 A Simple O(loglog(rank))Competitive Algorithm for the Matroid Secretary Problem by Feldman, Svensson, Zenklusen
 Friedgut's theorem via the logSob inequality (from Cuts in Cartesian Products of Graphs by Sachdeva and Tulsiani)
 Commuting time geometry of ergodic Markov chains by Doyle and Steiner