C&O Reading Group

 

 

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:

 

 

 

Sprint 2014 meetings are over. Happy rest of Summer everyone!

 

Upcoming Fall 14 Tentative Schedule has been announced.

Our meetings will take place on Mondays, 4-5:30pm, in MC 6486 (IQC room), unless otherwise specified.

·        Please subscribe to our mailing list to receive reminders and last-moment change notifications.

 

 

 

 

 

 

Date

Speaker

Topic

December 1, 2014

Laurent Poirrier

TBA

November 24, 2014

Abbas Mehrabian

TBA

November 17, 2014

Patrick Roncal

TBA

November 10, 2014

Zhihan Gao

TBA

November 3, 2014

Nishad Kothari

TBA

October 27, 2014

Cameron Marcott

TBA

October 20, 2014

Arash Haddadan

TBA

October 13, 2014

HOLIDAY

N/A

October 6, 2014

Andre Linhares

TBA

September 29, 2014

Harmony Zhan

TBA

September 22, 2014

Luis Ruiz

TBA

September 15, 2014

Miaolan Xie

TBA

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