C&O Reading Group
The C&O reading group is run by graduate students,
postdocs 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. Email 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:
Fall
14 seminar series
Our
meetings will take place on Mondays, 45:30pm, in MC 6486 (IQC room), unless otherwise
specified.
·
Please subscribe
to our mailing list to receive reminders and lastmoment change notifications.
Date 
Speaker 
Topic 
December
1, 2014 
Laurent
Poirrier 
TBA 
November
24, 2014 
Abbas Mehrabian 
TBA 
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 
Nishad
Kothari

TBA 
November
3, 2014 
Zhihan Gao 
“A
tutorial on the Lasserre hierarchy” By Rothvoß ( 
October
27, 2014 
Cameron
Marcott 
"Total Positivity: Tests and Parametrizations" by Fomin and Zelevinsky (Math. Intelligencer
2000) 
October
20, 2014 
Arash Haddadan 
by Skutella (SODA'15) 
October
13, 2014 
HOLIDAY 
N/A 
October
6, 2014 
Andre Linhares 
“Approximating
maxmin weighted Tjoins” 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 Lowrnk approximation for lowcoherence
matrices” 
July
21, 2014 
Andreas
Feldman 
“Improved approximation for
3dimensional 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 PrizeCollecting Steiner Tree and TSP" by
Archer, Bateni, Hajiaghayi,
and Karloff 
June
2, 2014 
John M.
Schanck 
"Structural Lattice Reduction:
Generalized WorstCase to AverageCase Reductions" by Gama, Izabachene, Nguyen and
Xie. 
May
26, 2014 
Ahmad
Abdi 
“The
weak perfect graph theorem” 
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
Quasibipartite 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 StochasticallyLocated
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” 
January
20, 2014 
Ningchuan Wang 
"Lower
Bound for Vertex Separator and Graph Partitioning Problem” 
January
13, 2014 
Andreas
Feldmann 
“A Survey of Fixed Parameter Approximation” 
December
2, 2013 
Ian
Post 
"A strongly polynomial algorithm for
generalized ﬂow maximization" by Laszlo Vegh (ArXiv13) 
November
25, 2013 
Nishad
Kothari 
“Eardecompositions of nonbipartite
matchingcovered graphs” 
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 HarPeled 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 BarreraCruz 
“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 SheraliAdams Hierarchy" Original
work (J. Cheriyan, K. Georgiou, Z. Gao and S. Singla ICALP13) 
June 19, 2013 
Zac Friggstad 
“The
BoundedRegret 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 fixfree codes" 
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 
"Linegraphs
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_4free
and prismfree planar matching covered graphs” 
April 17, 2013 
Sina Sadeghian 
"The Diffusion of Networking
Technologies" by
Goldberg and Liu (SODA'13) 
April 10, 2013 
Zac Friggstad 
"Approximating
kMedian via PseudoApproximation" by
Li and Svensson (manuscript) 
April 3, 2013 
Fidel BarreraCruz 
"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 JohnsonLinderstrauss Lemma" 
March 20, 2013 
Andreas
Feldmann 
"Prizecollecting
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 
"FixedParameter
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 
"EightFifth
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" 
February 6, 2013 
Sara Ahmadian 
"Randomized
PrimalDual 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 
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 semidefinite 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
5approximation 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
by Faigle,
Kern and Kuipers (Tech. Report 1998) 
October 25, 2012 
Sina Sadeghian 
"Approximate
k MSTs and k Steiner Trees via the PrimalDual Method and Lagrangean Relaxation" by by
Chudak, Roughagarden and
Williamson (IPCO01) 
October 18, 2012 
Vinayak Pathak 
"On a Linear Program for
MinimumWeight 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 
"MinMax Tree
Covers of Graphs" Talk will be based on "Improved
Approximation Algorithms for the MinMax 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" 
July 12, 2012 
Ahmad Abdi 
"Packing Odd
Circuit Covers" by Abdi and Guenin (2012) 
July 5, 2012 
Nishad Kothari 
by Johnsona,
Robertsonb, Seymoura, and
Thomasc (Journal of Combinatorial Theory 2001) 
June 28, 2012 
Sara Ahmadian 
"A
PrimalDual Approximation Algorithm for MinSum SingleMachine Scheduling
Problems" by Cheung and Shmoys (APPROX11) 
June 21, 2012 
Leanne Stuive 
"Matroidal
DegreeBounded 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 SingleSink BuyatBulk" by Goel
and Post (FOCS11) 
May 31, 2012 
Fidel BarreraCruz 
"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 PointSet is NPcomplete" by Lubiw
and Pathak (Arxiv12) 
May 17, 2012 
Zhihan
Gao 
"A Constant Factor Approximation for Minimum λEdgeConnected kSubgraph with Metric Costs" by Safari and Salavatipour (SIAM J. Discrete Math. 25 (3): 10891102, 2011) 
May 10, 2012 
Costis
Georgiou 
"Subexponential
Algorithms for SetCover" By Chlamtac,
Friggstad and Georgiou (Arxiv12) 
May 3, 2012 
Devanshu
Pandey 
By Chakrabarty
and Swamy, (IPCO11) 
April 26, 2012 
Zac
Friggstad 
"The Connected TJoin Problem
in General Metrics" by Cheriyan, Friggstad and Gao.
(2012) 
April 19, 2012 
Isaac
Fung 
by Andrews, Hajiaghayiy,
Karloff and Moitra (SODA11) 
April 12, 2012 
Soroush
Alamdari 
by Alamdari,
Fata, Smith (Arxiv12) 
March 29, 2012 
Sahil
Singla 
"PTAS for Eucledian kTSP and Orienteering Problems" This will be based on
"The
Orienteering Problem in the Plane Revisited" by Chen and HarPeled, SIAM J. Comput.
38(1): 385397 (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 
"EdgeDisjoint Paths in Planar
Graphs." Relevant reference: SéguinCharbonneua,ShephardFOCS
2011 
January 18, 2012 
Nishad Kothari 
"Width Parameters
for Directed Graphs" Relevant references: HunterKreutzer07, KintaliKothariKumar11. 
January 11, 2012 
Devanshu
Pandey 
by Immorlica,
Kalai, Lucier, Moitra, Postlewaite, and Tennenhotz (STOC11) 
December 14, 2011 
Costis
Georgiou 
“A tutorial on LiftandProject
Systems” 
December 7, 2011 
Leanne
Stuive 
“Improved
Mincut and Maxflow in
Planar Undirected Graphs” by Italiano,
Nussbaum, Sankowski and WulffNilsen
(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 PolyArc 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 
"MinMax Graph Partitioning and
SmallSet Expansion" by Bansal, Feige,
Krauthgamer, Makarychev, Nagarajan, Naor and Schwartz
(FOCS11) 
November 2, 2011 
Marco Blanco 
“PrimalDual
Schema and Lagrangian Relaxation for the
kLocationRouting Problem” by Carnes and Shmoys (APPROX11) 
October 26, 2011 
Fidel BarreraCruz 
"Threecoloring
trianglefree 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 
by Kaiser (Discrete & Computational Geometry, 1997) 
October 5, 2011 
Malcolm Sharpe 
“Jump
Number of TwoDirectional 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 BarreraCruz 
“On
Succinct Convex Greedy Drawing of 3Connected 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
onedimensional problem concerning random space filling" by Renyi (Publ. Math. Inst. Hung. Acad. Sci., 1958) 
June 7, 2011 
Marco Blanco 
"The
Matroid Median Problem" 
May 31, 2011 
Soroush Hosseini 
"Approximate
range searching in higher dimension" 
May 24, 2011 
Hadi Minooei 
“Multiunit Auctions
with Budget Limits” by Dobzinski, Lavi and Nisan
(FOCS08). 
May 17, 2011 
Elyot Grant 
“Tight lower bounds
for the size of epsilonnets” 
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 
by Cohen
and Nutov (Manuscript 2011). 
April 11, 2011 
Hadi Minooei 
"Multiunit
auctions with budgetconstrained 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 APXhardness 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" 
March 8, 2011 
Chaitanya Swamy 
“From
Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial
Auctions for Submodular Bidders" 
February 29, 2011 
Malcolm Sharpe 
"Dependent
Randomized Rounding via Exchange Properties of Combinatorial Structures" 
February 15, 2011 
Costis Georgiou 
“An
improved LPbased approximation for steiner tree” by Byrka, Grandoni, Rothvoß and Sanità (STOC11). 
February 8, 2011 
Jochen Könemann 
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 