C&O Reading Group

Mondays 4:30PM pizza; talk at 4:45PM.

The C&O reading group is run by graduate students, post-docs and faculty. Currently we are meeting once per week. The main purpose of our meetings is letting people know what we are working on or what we find interesting in recent and classic publications. Our meetings are also appropriate for practice talks or presentations of ongoing research. E-mail reminders for our presentations are sent on a weekly basis, one day prior to our meetings. If you want to give a talk, or to be added to our mailing list, or if you have any comment, please contact the host of this webpage.

Some guidelines, and how we think of our reading group:

· Talks are usually 1 hour long. This may include a 5-10 mins break.

· Talks end with a short discussion on relevant open problems.

· Speakers are free to choose their topics. Our focus though is on whatever touches on Algorithms or is relevant to Combinatorial Problems.

· Speakers do not assume any familiarity of the selected topic from the side of the audience. Presentations usually start with a high level exposition of the result, and finish with its technical contribution. At the end we try to have a 5-10 mins discussion of relevant open problems.

· Dates are assigned to speakers much in advance. Topics may not be announced till the last moment. If you choose a paper, please announce your intention to avoid conflicts.

Winter 16 term:

Our (pizza) meetings for W16 will take place on Mondays, 4:30-5:45pm, in MC 6486 , unless otherwise specified. Talks start at 4:45pm sharp.

· Please subscribe to our mailing list to receive reminders and last-moment change notifications (hwolkowicz@uwaterloo.ca).

Date	Speaker	Topic
Apr. 4, 2016	Nathan Lindzey	Parallel algorithms for perfect matchings abstract
March 21, 2016	Gabriel Gauthier-Shalom	The mathematics of juggling
March 14, 2016	David Lou	Principal Angles and Vectors of Two Subspaces
March 07, 2016	Nishad Kothari	The Perfect Matching Polytope and Solid Graphs, abstract
February 29, 2016	Julian Romero	Fourier Analysis, Chordal Graphs and Sums of Squares
February 22, 2016	Yan Xu	Title: Counting walks on Graphs, abstract
February 08, 2016		T.B.A
February 01, 2016		T.B.A
January 25, 2016	Gabriel Gauthier-Shalom	postponed to Mar 21/16
January 18, 2016	Patrick Dornian	A brief introduction to the h-vector and its specializations, and abstract
January 11, 2016		T.B.A
January 04, 2016	N\A	N\A
November 30, 2015	Fernando Afonso	“A branch-and-cut-and-price algorithm for the Pollution Routing Problem”
November 23, 2015	Garnet Akeyr	"Aligned curves and height functions on Jacobians of curves" Relevant paper Holmes D., (arXiv:1402.0647)
November 16, 2015	Elisabeth Gaar	“Modifying the Lovász Theta Function for Obtaining Upper Bounds on the Stability Number” Original and joint work with Franz Rendl.
November 09, 2015	Nargiz Kalantarova	“Low rank matrix recovery using Schatten-p quasi norm minimization” by M.-C. Yue and A. M.-C. So, (arXiv:1209.0377v4)
November 02, 2015	André Linhares	“On the Minimum-Cost Chain-Constrained Spanning Tree Problem” Original and joint work with Chaitanya Swamy. Relevant papers [1].
October 26, 2015	Randy Yee	“ECDLP and Improved Baby-Step Giant-Step” by Galbraith, S. D., Wang, P. and Zhang, F. [1],
October 19, 2015	Pavel Shuldiner	“Plane Partitions & Some Sweet Generating Functions” by Kamioka, S. (arXiv15)
October 05, 2015	N\A	N\A
September 28, 2015	N\A	N\A
September 21, 2015	Mehdi Karimi	"A gentle overview of SDP representable sets and SDP applications" By Vanderberghe, L., and Boyd S. ( SIAM Review 1996) and Goemans, M. X. and Williamson D. P. (JACM 1995)
September 14, 2015	N\A	N\A
July 27, 2015	Hao Sun	“Separating Maximally Violated Comb Inequalities in Planar Graphs” By Fleischer and Tardos (Math of OR 1999)
July 13, 2015	Alan Arroyo	“Drawing complete graphs with an specified set of crossings” By Kynčl (Discrete & Computational Geometry 2011)
July 6, 2015	Harmony Zhan	“Some constructions of integral graphs” By Mohammadian and Tayfeh-Rezaie (Linear and Multilinear Algebra 2010)
June 29, 2015	Cameron Marcott	"Combinatorial Geometries, Convex Polyhedra, and Schubert Cells" By Gelfand, Goresky, MacPherson and Serganova (Adv in Math 1987)
June 22, 2015	Luis Ruiz	“Fast Lattice Point Enumeration With Minimal Overhead” By Micciancio and Walter (IACR Cryptology Archive 2014)
June 15, 2015	Dessalegn Hirpa	"The generalized trust region subproblem (GTRS)" By Pong and Wolkovicz (Comp. Opt. and Appl 14)
June 8, 2015	Arash Haddadan	“Bin packing and discrepancy theory” By Eisenbrand, Pálvölgyi and Rothvoß (SODA11)
June 1, 2015	Andre Linhares	“Changing Bases: Multistage Optimization for Matroids and Matchings” By Gupta, Talwar, and Wieder (ICALP14)
May 25, 2015	Isaac Fung	"Online Network Design Algorithms via Hierarchical Decompositions" By S. Umboh (arXiv14)
May 11, 2015	Julian Romero	“A Positive Semidefinite Approximation for the cone of Non-negative Polynomials” By J. Romero and M. Velasco (arXiv14)
May 4, 2015	Jalaj Upadhyay	“Differential Privacy in the Streaming Model” Original work. Relevant papers [1], [2].
April 6, 2015	Miaolan Xie	“Cone, Polytope and Ellipsoid” By F. John
March 30, 2015	Alexander Lange	“Maximizing Social Influence in Nearly Optimal Time" By Borgs, Brautbar, Chayes, and Lucier (SODA14)
March 23, 2015	Kanstantsin Pashkovich	“The Power of Deferral: Maintaining the Constant-Competitive Steiner Tree" by Gu, Gupta and Kumar (arXiv 2013)
March 16, 2015	John M. Schanck	"The Closest Vector Problem with Preprocessing" By Dadush, egev, Stephens-Davidowitz (arXiv 2014)
March 9, 2015	Tor Myklebust	“Interior-point methods in convex optimisation" by Myklebust and Tuncel (arXiv14)
March 2, 2015	Umang Bhaskar	“Market Equilibria in Polynomial time for Fixed Number of Goods or Agents” by Devanur and Kannan
February 23, 2015	Sara Ahmadian	“Achieving Anonymity via Clustering” By Aggarwal, Feder, Kenthapadi, Khuller, Panigrahy, Thomas, Zhu (ACM Transactions on Algorithms 2010)
February 16, 2015	N/A	N/A (reading week)
February 9, 2015	Andreas Feldmann	“Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs” By Chekuri, Ene, Vakilian (ICALP12)
February 2, 2015	Alan Arroyo	“Bishellable Drawings of Kn” By Ábrego, Aichholzer, Fernández-Merchant, McQuillan, Mohar, Mutzel, Ramos, Richter, Vogtenhuber (arXiv 2013)
January 26, 2015	Nishad Kothari	“Near-bipartite bricks” Relevant links [1], [2],[3]
January 19, 2015	Mehdi Karimi	“Statistical-Computational Tradeoffs in Planted Problems with a Growing Number of Clusters” By Chen and Xu (arXiv 2014)
January 12, 2015	Ahmad Abdi	“A quick note on matroids” Original and joint work with Peter Nelson.
December 1, 2014	Laurent Poirrier	“Linear Programming Crossover” By Megiddo (ORSA Journal on Computing 1991)
November 24, 2014	Cancelled	Cancelled
November 17, 2014	Patrick Roncal	"Fast Computing Betweenness Centrality with Virtual Nodes on Large Sparse Networks." By Yang and Chen (PLoS ONE 2011)
November 10, 2014	Abbas Mehrabian	“A Graph-Theoretic Game and Its Application to the k-Server Problem “ By Alon, Karp, Peleg, and West ( SIAM J. on Comp. 1993)
November 3, 2014	Zhihan Gao	“A tutorial on the Lasserre hierarchy” By Rothvoß ( MAPSP Tutorial, 2013)
October 27, 2014	Cameron Marcott	"Total Positivity: Tests and Parametrizations" by Fomin and Zelevinsky (Math. Intelligencer 2000)
October 20, 2014	Arash Haddadan	“The ring loading problem” by Skutella (SODA'15)
October 13, 2014	HOLIDAY	N/A
October 6, 2014	Andre Linhares	“Approximating max-min weighted T-joins” by Iwata and Ravi (OR letters 2013)
September 29, 2014	Harmony Zhan	“Constructing infinite bipartite Ramanujan graphs” By Marcus, Spielman and Srivastava (FOCS13)
September 22, 2014	Luis Ruiz	“On the (Im)possibility of Obfuscating Programs” By Barak et al. (CRYPTO01)
September 15, 2014	Miaolan Xie	“A gentle introduction to Spectral Clustering” By von Luxburg (Statistics and Computing, 17 (4), 2007)
July 28, 2014	Jalaj Upadhyay	“Differentially Private Low-rnk approximation for low-coherence matrices” Relevant references [1], [2].
July 21, 2014	Andreas Feldman	“Improved approximation for 3-dimensional matching via bounded pathwidth local search” By Cygan (FOCS13)
July 14, 2014	Linda Farczadi	“Stable marriage with general preferences” By Farczadi, Georgiou and Könemann (SAGT14)
July 7, 2014	N/A	Open Problem Session
June 30, 2014	HOLIDAY	N/A
June 23, 2014	Saeed Rezaei	“On the odd cycles of normal graphs” By De Simone and Korner (Discrete Applied Mathematics 1999)
June 16, 2014	Vinayak Pathak	“Shortest reconfiguration paths in the solution space of Boolean formulas” By Mouawad, Nishimura, Pathak, Raman (arXiv 2014)
June 9, 2014	Ian Post	"Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP" by Archer, Bateni, Hajiaghayi, and Karloff
June 2, 2014	John M. Schanck	"Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions" by Gama, Izabachene, Nguyen and Xie.
May 26, 2014	Ahmad Abdi	“The weak perfect graph theorem” Relevant references [1], [2]
May 19, 2014	HOLIDAY	N/A
May 12, 2014	Sara Ahmadian	“New approximability results robust k median problem” By Bhattacharya, Chalermsook, Mehlhorn, Neumann (arXiv 2013)
May 5, 2014	Mehdi Karimi	“Exponential Lower Bounds for Polytopes in Combinatorial Optimization” By Fiorini, Massar, Pokutta, Yiwary and de Wolf (arXiv11)
March 31, 2014	Mohammad Shadravan	"A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs" (original work)
March 24, 2014	Luis Ruiz	“Lattice Reduction Algorithms: Theory and Practice” by Phong Q. Nguyen (EUROCRYPT11) [additional relevant reference]
March 17, 2014	Alex Lange	"Approximation Algorithms for Fragmenting a Graph against a Stochastically-Located Threat" by Gwen Spencer and David Shmoys (WAOA 2011).
March 10, 2014	Narges Simjour	"Clustering with Local Restrictions" by Lokshtanov and Marx, (ICALP 2011)
March 3, 2014	Cameron Marcott	“Computing Schubert Polynomials” by N. Bergeron and S. Billey
February 24, 2014	Harmony Zhan	“Complex Hadamard Matrices, Instantaneous Uniform Mixing and Cubes” by A. Chan. (arXiv 2013)
February 10, 2014	Andre Linhares	"Fast approximation algorithms for the diameter and radius of sparse graphs" by Roditty and Williams (STOC 2013)
January 27, 2014	Linda Farczadi	“A polyhedral approach to stable matchings” Relevant reference
January 20, 2014	Ningchuan Wang	"Lower Bound for Vertex Separator and Graph Partitioning Problem” Relevant reference
January 13, 2014	Andreas Feldmann	“A Survey of Fixed Parameter Approximation” Relevant reference
December 2, 2013	Ian Post	"A strongly polynomial algorithm for generalized ﬂow maximization" by Laszlo Vegh (ArXiv13)
November 25, 2013	Nishad Kothari	“Ear-decompositions of nonbipartite matching-covered graphs” References: [1], [2].
November 18, 2013	Abbas Mehrabian	“Quantum query complexity of some graph problems” by Durr, Heiligman, Hoyer and Mhalla (SIAM J. Comput. 2006)
November 11, 2013	Isaac Fung	“Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems” by Har-Peled and Raichel (STOC13)
November 4, 2013	Jason Liu	“Constant Integrality Gap LP formulations of Unsplittable Flow on a Path” by Anagnostopoulos, Grandoni, Leonardi, Wiese (IPCO13)
October 28, 2013	Jalaj Upadhyay	“Random Projections, Graph Sparsification, and Differential Privacy” by Upadhyay (ePrint13)
October 21, 2013	Fidel Barrera-Cruz	“On how to draw a graph” by W.T. Tutte (result outline by J. Geelen). If time allows it, some applications will be discussed.
October 7, 2013	Mohammad Shadravan	"Sparsest cut on bounded treewidth graphs: algorithms and hardness results" by Gupta, Talwar, Witmer (STOC13)
September 30, 2013	Ahmad Abdi	"On the directed Steiner tree polyhedron", by Abdi, Feldmann, Guenin, Könemann and Sanita
September 25, 2013	Abbas Mehrabian	“Basic Network Creation Games” by Alon, Demaine, Hajiaghayi and Leighton (SiDMa13)
September 18, 2013	Venus Lo	“Max flows in O(nm) time or better” by J.B. Orlin (STOC13)
July 24, 2013	Sara Ahmadian	“Simultaneous Source Location” by Andreev, Garrod, Maggs and Meyerson (APPROX04)
July 17, 2013	Srinivasan Arunachalam	“A fast Quantum mechanical algorithm for database Search” by Lov K. Grover (STOC '96)
July 10, 2013	Linda Farczadi	"Approximation of maximum stable marriage" by Zoltán Király
July 3, 2013	Harmony Zhan	“Graph Reconstruction - A Survey” by Bondy and Hemminger (Journal of Graph Theory 1977)
June 26, 2013	Zhihan Gao	"On Integrality Ratios for Assymetric TSP in the Sherali-Adams Hierarchy" Original work (J. Cheriyan, K. Georgiou, Z. Gao and S. Singla ICALP13)
June 19, 2013	Zac Friggstad	“The Bounded-Regret Vehicle Routing Problem (BVRP)” Original work (Z. Friggstad and C. Swamy).
June 12 ,2013	Vinayak Pathak	"Reconfiguration problems: A survey" A survey based on [1].
June 5, 2013	Ehsan Ebrahimzadeh	"Sufficient conditions on existence of fix-free codes" A survey, based on [1],[2]
May 29, 2013	Elaheh Fata	"Approximation Algorithms for the Bottleneck Asymmetric Travelling Salesman Problem" by An, Kleinberg and Shmoys (APPROX10)
May 22, 2013	Seyed Saeed Rezaei	"Line-graphs of cubic graphs are normal" by Zsolt Patakfalvi (arXiv08)
May 15, 2013	Mohammad Shadravan	“Directed Steiner Tree and the Lasserre Hierarchy" by T. Rothvoß (arXiv12)
May 8, 2013	Ian Post	"Linear vs Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds" by Fiorini, Massar, Pokutta, Tiwary and de Wolf (STOC12)
May 1, 2013	Nishad Kothari	“K_4-free and prism-free planar matching covered graphs” Relevant papers [1], [2], [3], [4]
April 17, 2013	Sina Sadeghian	"The Diffusion of Networking Technologies" by Goldberg and Liu (SODA'13)
April 10, 2013	Zac Friggstad	"Approximating k-Median via Pseudo-Approximation" by Li and Svensson (manuscript)
April 3, 2013	Fidel Barrera-Cruz	"Morphing Planar Graph Drawings with a Polynomial Number of Steps" by Alamdari, Angelini, Chan, Di Battista, rati, Lubiw, atrignani, Roselli, Singla, Wilkinson (SODA13)
March 27, 2013	Jalaj Upadhyay	"Privacy and the Johnson-Linderstrauss Lemma" relevant papers [1], [2]
March 20, 2013	Andreas Feldmann	"Prize-collecting Steiner Problems on Planar Graphs" by Bateni, Chekuri, Ene, Hajiaghayi, Korula and Marx (SODA11)
March 13, 2013	Guru Prashanth	"Catch Them If You Can: How to Serve Impatient Users" by Cygan, Englert, Gupta, Mucha and Sankowski (ITCSC13)
March 6, 2013	Narges Simjour	"Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset" by R. Chitnis, M. Hajiaghayi, and D. Marx (SODA12)
February 27, 2013	Zhihan Gao	"Eight-Fifth Approximation for TSP Paths" by A. Sebö (To appear in IPCO 2013)
February 13, 2013	Vinayak Pathak	"Using partial cubes to find shortest paths in sublinear time" Related references [1], [2], [3], [4]
February 6, 2013	Sara Ahmadian	"Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching" by Devanur, Jain and Kleinberg (SODA13)
January 30, 2013	Linda Farczadi	"Balanced Outcomes in Social Exchange Networks" by Kleiberg and Tardos (STOC08)
January 23, 2013	Ahmad Abdi	From Pfaffian Orientations to Packing and Covering Related papers [1], [2], [3], [4], [5]
January 16, 2013	Venkatesh Raman	"A 4k^2 kernel for feedback vertex set" by Thomasse (ACM Transaction on Algorithms 2010)
December 13, 2012	Zhihan Gao	"Integrality gaps of linear and semi-definite programming relaxations for Knapsack" by Karlin, Mathieu, and Nguyen (IPCO'11)
December 6, 2012	Leanne Stuive	"A Constructive Version of Lehman's Theorem and Applications in Flow Problems" Thesis related subject.
November 29, 2012	Guru Prashanth	"Welfare and Profit Maximization with Production Costs" by Blum, Gupta, Mansour, and Sharma (FOCS11)
November 22, 2012	Andreas Feldmann	"Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations" by Goemans, Olver, Rothvoß and Zenklusen (FOCS12)
November 15, 2012	Sara Ahmadian	"A 5-approximation algorithm for capacitated facility location problem" by Bansal, Garg and Gupta (ESA12)
November 8, 2012	Olivier Durand de Gevigney	"Basic Packing of Arborescences" by Durand de Gevigney, Nguyen and Szigeti (arXiv12)
November 1, 2012	Linda Farczadi	"An efficient algorithm for nucleolus and prekernel computation in some classes of TU-games" by Faigle, Kern and Kuipers (Tech. Report 1998)
October 25, 2012	Sina Sadeghian	"Approximate k -MSTs and k -Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation" by by Chudak, Roughagarden and Williamson (IPCO01)
October 18, 2012	Vinayak Pathak	"On a Linear Program for Minimum-Weight Triangulation" by Yousefi and Young (SODA12)
October 11, 2012	Nishad Kothari	"Matching Structure and the Matching Lattice" by Lovász (JCT Series B, 1987)
October 4, 2012	Devanshu Pandey	"Min-Max Tree Covers of Graphs" Talk will be based on "Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems" by Reza khani and Salavatipour. (APPROX11) , and his own research.
September 27, 2012	Abbas Mehrabian	"The hitting and cover times of random walks on finite graphs using local degree information" by Ikeda, Kubo and Yamashita (Theor. Comput. Sci. 2009)
September 20, 2012	Zac Friggstad	"Advances on Matroid Secretary Problems: Free Order Model and Laminar Case" by Patrick Jaillet, José A. Soto, Rico Zenklusen (arXiv12)
July 26, 2012	Hadi Minooei	"Optimal auctions with correlated bidders are easy" by Dobzinski, Fu and Kleinberg (STOC11)
July 19, 2012	Abbas Mehrabian	"Constructive Discrepancy Minimization by Walking on The Edges" by Lovett and Meka (FOCS12)
July 12, 2012	Ahmad Abdi	"Packing Odd Circuit Covers" by Abdi and Guenin (2012)
July 5, 2012	Nishad Kothari	"Directed Tree-width" by Johnsona, Robertsonb, Seymoura, and Thomasc (Journal of Combinatorial Theory 2001)
June 28, 2012	Sara Ahmadian	"A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems" by Cheung and Shmoys (APPROX11)
June 21, 2012	Leanne Stuive	"Matroidal Degree-Bounded Minimum Spanning Trees" by Zenklusen (SODA12)
June 14, 2012	Laura Sanita	"Extensions and limits to vertex sparsification" by Leighton and Moitra (STOC10)
June 7, 2012	Guru Prashanth	"One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk" by Goel and Post (FOCS11)
May 31, 2012	Fidel Barrera-Cruz	"Graph Connectivities, Network Coding, and Expander Graphs" by Cheung, Lau and Leung (FOCS11)
May 24, 2012	Vinayak Pathak	"Flip Distance Between Two Triangulations of a Point-Set is NP-complete" by Lubiw and Pathak (Arxiv12)
May 17, 2012	Zhihan Gao	"A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs" by Safari and Salavatipour (SIAM J. Discrete Math. 25 (3): 1089-1102, 2011)
May 10, 2012	Costis Georgiou	"Subexponential Algorithms for Set-Cover" By Chlamtac, Friggstad and Georgiou (Arxiv12)
May 3, 2012	Devanshu Pandey	"Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems" By Chakrabarty and Swamy, (IPCO11)
April 26, 2012	Zac Friggstad	"The Connected T-Join Problem in General Metrics" by Cheriyan, Friggstad and Gao. (2012)
April 19, 2012	Isaac Fung	"Capacitated Metric Labeling" by Andrews, Hajiaghayiy, Karloff and Moitra (SODA11)
April 12, 2012	Soroush Alamdari	"Min-Max Latency Walks" by Alamdari, Fata, Smith (Arxiv12)
March 29, 2012	Sahil Singla	"PTAS for Eucledian k-TSP and Orienteering Problems" This will be based on "The Orienteering Problem in the Plane Revisited" by Chen and Har-Peled, SIAM J. Comput. 38(1): 385-397 (2008)
March 22, 2012	Marco Blanco	“Bin Packing via Discrepancy of Permutations” by Eisenbrand, Pálvölgyi, Rothvoß (SODA11)
March 8, 2012	Hadi Minooei	“An impossibility result for truthful combinatorial auctions with submodular valuations” by Dobzinski, (STOC11)
March 1, 2012	Ahmad Abdi	“Packing Binary Clutters and the Cycling Conjecture” A survey. Relevant reference Seymour77
February 16, 2012	Abbas Mehrabian	“Testing Properties of Directed Graphs: Acyclicity and Connectivity” by Bender and Ron ICALP 2000 and RSA 2002
February 8, 2012	Sara Ahmadian	“Constant Factor Approximation Algorithm forthe Knapsack Median Problem” By Amit Kumar (SODA12).
February 1, 2012	Vinayak Pathak	"On Range Searching in the Group Model and Combinatorial Discrepancy." by Kasper Green Larsen (FOCS11)
January 25, 2012	Leanne Stuive	"Edge-Disjoint Paths in Planar Graphs." Relevant reference: Séguin-Charbonneua,Shephard-FOCS 2011
January 18, 2012	Nishad Kothari	"Width Parameters for Directed Graphs" Relevant references: Hunter-Kreutzer07, Kintali-Kothari-Kumar11.
January 11, 2012	Devanshu Pandey	“Dueling Algorithms” by Immorlica, Kalai, Lucier, Moitra, Postlewaite, and Tennenhotz (STOC11)
December 14, 2011	Costis Georgiou	“A tutorial on Lift-and-Project Systems”
December 7, 2011	Leanne Stuive	“Improved Mincut and Maxflow in Planar Undirected Graphs” by Italiano, Nussbaum, Sankowski and Wulff-Nilsen (STOC11)
November 30, 2011	Nima Mousavi	“Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs” by Goel, Kapralov and Khanna (STOC10)
November 23, 2011	Soroush Alamdari	“Planar and Poly-Arc Lombardi Drawings” by Duncan, Eppstein, Goodrich, Kobourov and Löffler (Graph Drawing 2011)
November 16, 2011	Zac Friggstad	"Santa Claus Schedules Jobs on Unrelated Machines" by Ola Svenssonn (STOC11)
November 9, 2011	Abbas Mehrabian	"Min-Max Graph Partitioning and Small-Set Expansion" by Bansal, Feige, Krauthgamer, Makarychev, Nagarajan, Naor and Schwartz (FOCS11)
November 2, 2011	Marco Blanco	“Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem” by Carnes and Shmoys (APPROX11)
October 26, 2011	Fidel Barrera-Cruz	"Three-coloring triangle-free planar graphs in linear time" by Dvorak, Kawarabayashi and Thomas (SODA09)
October 19, 2011	Hadi Minooei	"Towards Optimal Bayesian Algorithmic Mechanism Design" by Bei and Huang (SODA11)
October 12, 2011	Malcolm Sharpe	“Transversals of d-Intervals” by Kaiser (Discrete & Computational Geometry, 1997)
October 5, 2011	Malcolm Sharpe	“Jump Number of Two-Directional Orthogonal Ray Graphs” by Soto and Telha (IPCO11)
September 21, 2011	Isaac Fung	“Approximating Graphic TSP by Matchings” by Mömke and Svensson (FOCS11)
September 14, 2011	Costis Georgiou	“How bad is forming your own opinion?” by Bindel, Kleinberg and Oren (FOCS11)
July 26, 2011	Abbas Mehrabian	"Constructive Algorithms for Discrepancy Minimization" by Nikhil Bansal.
July 12, 2011	Malcolm Sharpe	"Matroid matching: the power of local search" by Lee, Sviridenko and Vondrak (STOC10)
July 5, 2011	Fidel Barrera-Cruz	“On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs” by He and Zhang (SODA11)
June 28, 2011	Jochen Könemann	“Set Cover with Ordered Replacement - Additive and Multiplicative Gaps” by Eisenbrand, Kakimura, Rothvoß, Sanita (IPCO11)
June 21, 2011	Costis Georgiou	"On a one-dimensional problem concerning random space filling" by Renyi (Publ. Math. Inst. Hung. Acad. Sci., 1958)
June 7, 2011	Marco Blanco	"The Matroid Median Problem" by Krishnaswamy, Kumar, Nagarajan, Sabharwal, Saha (SODA11).
May 31, 2011	Soroush Hosseini	"Approximate range searching in higher dimension" by Chazelle, Liu and Magen (CGTA08).
May 24, 2011	Hadi Minooei	“Multi-unit Auctions with Budget Limits” by Dobzinski, Lavi and Nisan (FOCS08).
May 17, 2011	Elyot Grant	“Tight lower bounds for the size of epsilon-nets” by Pach and Tardos (SoCG11).
May 10, 2011	Abbas Mehrabian	"Computing the Independence Number of Intersection Graphs" by Fox and Pach (SODA11).
May 3, 2011	Malcolm Sharpe	"Cohen and Nutov's Application of Zelikovsky's Greedy Heuristic to Tree Augmentation, with Matroid Generalization" Original work. Relevant references: Zelikovsky 1995, Cohen, Nutov 2011
April 18, 2011	Malcolm Sharpe	"A (1 + ln 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius" by Cohen and Nutov (Manuscript 2011).
April 11, 2011	Hadi Minooei	"Multi-unit auctions with budget-constrained bidders" by Borgs, Chayes, Immorlica, Mahdian and Saberi (EC05).
April 4, 2011	Costis Georgiou	“On the Approximability of Budget Feasible Mechanisms" by Chen, Gravin and Lu (SODA11).
March 29, 2011	Abbas Mehrabian	"Faster generation of random spanning trees" by Kelner, and Madry (FOCS09).
March 22, 2011	Elyot Grant	"Some New APX-hardness results for Geometric Set Cover Problems" Original work. (jointly with Timothy Chan)
March 15, 2011	Krystal Guo	"Prizing on Paths: A PTAS for the Highway Problem" by Grandoni and Rothvoß (SODA11)
March 8, 2011	Chaitanya Swamy	“From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders" by Sughmi, Roughgarden and Yan (STOC11).
February 29, 2011	Malcolm Sharpe	"Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures" by Chekuri, Vondrak, and Zenklusen. (FOCS 2010).
February 15, 2011	Costis Georgiou	“An improved LP-based approximation for steiner tree” by Byrka, Grandoni, Rothvoß and Sanità (STOC11).
February 8, 2011	Jochen Könemann	"Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound" by Chakrabarty, Könemann and Pritchard (Operations Letters 2010)
February 1, 2011	Costis Georgiou	“Fooling strong LP and SDP hierarchies for Vertex Cover” Relevant references: G., Magen, Tourlakis 2009, Benabbas, Chan, G., Magen 2010