CombOpt Reading Group
The purpose of our reading group is for students to learn new things, to learn how to present research to their peers, and to possibly pick up a research question or two in the process.
Each month or two we have a new topic of combinatorial optimization.
 When:
 Fridays, 1:00 pm
 Where:
 MC 5479
To stay up to date please subscribe to our mailing list here.
Please do not hesitate to contact Leanne Stuive or Kanstantsin Pashkovich in case you have any questions or suggestions.
Current Topic
Topic: Multiplicative Weight Updates.
 1 Jun 2018

Julian Romero
Multiplicative Weight Updates as Mirror Descent.
 8 Jun 2018

Zhuan Khye Koh
Weighted majority.
 15 Jun 2018

Justin Toth
"Randomized Rounding without Solving the Linear Program", 1995
by Neal E. Young
 22 Jun 2018

Jochen Koenemann
Packing and covering LP's.
 29 Jun 2018
 ISMP 2018. This Friday we have no talks.
 6 Jul 2018
 ISMP 2018. This Friday we have no talks.
 13 Jul 2018

Akshay Ramachandran
Entropy, information and other interpretations.
 20 Jul 2018

Sharat Ibrahimpur
"Nearly LinearTime Approximation Schemes for Mixed Packing/Covering and FacilityLocation Linear Programs", 2014
by Neal E. Young
"Nearlinear time approximation schemes for some implicit fractional packing problems", 2017
by Chandra Chekuri and Kent Quanrud
 27 Jul 2018

Sina Rezazadeh
Matrix multiplicative weight updates.
 3 Aug 2018

Hong Zhou
"Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates", 2015
by Zeyuan AllenZhu, Zhenyu Liao, Lorenzo Orecchia
Past Topics
Topic: Discrepancy.
 13 Jan 2017

Kanstantsin Pashkovich
"“Integermaking” theorems", 1981
by József Beck and Tibor Fiala
BeckFiala Theorem can also be found in Chapter 4, "Geometric Discrepancy", Jiří Matoušek. This book is available online through UWaterloo Library.
 20 Jan 2017

Sanchit Kalhan
"Roths estimate of the discrepancy of integer sequences is nearly sharp", 1981
by József Beck
Partial Coloring Lemma can also be found in Chapter 4, "Geometric Discrepancy", Jiří Matoušek. This book is available online through UWaterloo Library.
 27 Jan 2017

Sina Rezazadeh
"Six standard deviations suffice", 1985
by Joel Spencer
Entropy Method and Spencer's Theorem can also be found in Chapter 4, "Geometric Discrepancy", Jiří Matoušek. This book is available online through UWaterloo Library.
 03 Feb 2017

Julian Romero
"Constructive algorithms for discrepancy minimization", 2010
by Nikhil Bansal
 10 Feb 2017

Ahmad Abdi
"Constructive discrepancy minimization by walking on the edges", 2012
by Shachar Lovett and Raghu Meka
 17 Feb 2017

Mehdi Karimi
"An algorithm for Komlós conjecture matching Banaszczyk's bound", 2016
by Nikhil Bansal, Daniel Dadush, Shashwat Garg
 24 Feb 2017

Nathan Lindzey
"Constructive Discrepancy Minimization for Convex Sets", 2014
by Thomas Rothvoss
Here is the talk Constructive Discrepancy Minimization for Convex Sets by Thomas Rothvoss.
 3 Mar 2017

André Linhares
"The entropy rounding method in approximation algorithms", 2012
by Thomas Rothvoss
 10 Mar 2017

This Friday we have no talks. However if you want to watch a talk on Discrepancy, here is a recent talk by Nikhil Bansal "Dicrepancy beyond Partial Colorings".
Topic: Ramanujan Graphs and Interlacing Families.
 17 Mar 2017

Maxwell Levit
"Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees", 2013
by Adam Marcus, Daniel A. Spielman, Nikhil Srivastava
Ramanujan graphs, 2lifts, spectral expansions and graph expansions will be defined. We will see Theorems of Heilmann and Lieb and Theorems of Godsil on matching polynomials.
 24 Mar 2017

Leanne Stuive
"Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
", 2013
by Adam Marcus, Daniel A. Spielman, Nikhil Srivastava
We will see core results on interlacing polynomials and stable polynomials.
 31 Mar 2017

Mehdi Karimi
"TwiceRamanujan Sparsifiers", 2014
by Joshua Batson, Daniel A. Spielman, Nikhil Srivastava
For a better understanding of the "barrier functions" argument, please view the talk Graph Sparsification II: Barrier Functions and Rankone Updates by Nikhil Srivastava.
Here are two further talks by Nikhil Srivastava: Graph Sparsification I: Sparsification via Effective Resistances and Graph Sparsification III: Interlacing Polynomials and Ramanujan Graphs of Every Degree. Please also take a look at the blog posts by Nikhil Srivastava, for example the post on Discrepancy, Graphs, and the KadisonSinger Problem.
 7 Apr 2017

David Wagner
"Interlacing Families II: Mixed Characteristic Polynomials and the KadisonSinger Problem", 2013
by Adam Marcus, Daniel A. Spielman, Nikhil Srivastava
An overview of results and applications.
 14 Apr 2017

Good Friday. This Friday we have no talks.
 21 Apr 2017

Question Session. We discuss questions related to the topics of this term.
Topic: Traveling Salesman.
 5 May 2017

Laura Sanità
Classic results and overview of the results from the chosen papers.
 15 May 2017
(Monday)

Matthew Buckley
"Approximating Graphic TSP by Matchings", 2011
by Tobias Mömke, Ola Svensson
Here is a talk by Naveen Garg Approximating Graphic TSP by Matchings.
 19 May 2017

Justin Toth
"Shorter Tours by Nicer Ears: 7/5approximation for graphic TSP, 3/2 for the path version, and 4/3 for twoedgeconnected subgraphs", 2012
by András Sebő, Jens Vygen
 26 May 2017

André Linhares
"On the metric st path Traveling Salesman Problem", 2014
by Zhihan Gao
 2 June 2017

Martin Groß
"Better stTours by Gao Trees", 2015
by Corinna Gottschalk, Jens Vygen
Here is a talk by Jens Vygen Reassembling trees for the traveling salesman, which leads up to the result of Corinna Gottschalk and Jens Vygen. Please, note that recently Frans Schalekamp, András Sebö, Vera Traub and Anke van Zuylen provided a short proof of the key structural result of Corinna Gottschalk and Jens Vygen.
 9 June 2017

András Sebö
"The Salesman's Improved Paths: A 3/2+1/34 Approximation", 2016
by András Sebö, Anke van Zuylen
The algorithm, the main proof of the analysis and the intuition behind its ingredients will be explained, including the gain of using Gottschalk and Vygen's particular convex combination of spanning trees, and how finally Frans Schalekamp, András Sebő, Vera Traub and Anke van Zuylen in "Layers and matroids for the travelling salesman's paths" (April 2017) finally managed to use matroid union for a simple algorithmic proof of this particular convex combination.
 16 June 2017

Quincy LapKwan Lam
"PolynomialTime Separation of a Superclass of Simple Comb Inequalities", 2006
by Lisa K. Fleischer, Adam N. Letchford and Andrea Lodi
 23 June 2017

Questions and Discussion Session with Sylvia Boyd and András Sebö.
 30 June 2017

IPCO break. This Friday we have no talks.
 7 July 2017

Akshay Ramachadran
"An O(log n/ log log n)approximation Algorithm for the Asymmetric Traveling Salesman Problem", 2010
by Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi
Here is a talk by Shayan Oveis The Asymmetric Traveling Salesman Problem.
 14 July 2017

Zhuan Khye Koh
"Approximating ATSP by Relaxing Connectivity", 2015
by Ola Svensson
Here is a talk by Ola Svensson Approximating ATSP by Relaxing Connectivity.

21 July 2017

SiGMa break. This Friday we have no talks.
 28 July 2017

Sharat Ibrahimpur
"Constant Factor Approximation for ATSP with Two Edge Weights", 2015
by Ola Svensson, Jakub Tarnawski, László A. Végh
 4 Aug 2017

Akshay Ramachadran and Julian Romero
"EffectiveResistanceReducing Flows, Spectrally Thin Trees, and Asymmetric TSP", 2014
by Nima Anari, Shayan Oveis Gharan
The talk does not assume any previous reading.
Further reading: Please take a look at the Nikhil Srivastava's blog Discrepancy, Graphs, and the KadisonSinger Problem.
Please also take a look at the course Recent Developments in Approximation Algorithms by Shayan Oveis Gharan. In Lectures 18 and 19 of this course, the results from the above paper were presented.
Topic: Stable Polynomials, Hyperbolic Polynomials and Optimization.
 10 Jan 2018
(Wednesday,
1:00 pm)

Leanne Stuive
"Hyperbolic Programs, and Their Derivative Relaxations", 2006
by James Renegar
Further reading: Please take a look at the lecture notes for the course
The Geometry of Polynomials in Algorithms, Combinatorics, and Probability (Lecture 11) taught by Nikhil Srivastava and the lecture notes for the course
Algebraic Techniques and Semidefinite Optimization (Lecture 7) taught by Pablo Parrilo. Here is the thesis of Tor Myklebust
"Geometry of convex sets arising from hyperbolic polynomials". Here are "Notes on Hyperbolicity Cones" by Petter Brändén.
 12 Jan 2018

Leanne Stuive
"Hyperbolic Programs, and Their Derivative Relaxations", 2006
by James Renegar
 19 Jan 2018

Akshay Ramachadran
"Multivariate stable polynomials: theory and applications", 2011
by David Wagner
 26 Jan 2018

Akshay Ramachadran
"Multivariate stable polynomials: theory and applications", 2011
by David Wagner
 2 Feb 2018

Sina Rezazadeh
"Hyperbolic Polynomials and Convex Analysis", 2001
by Heinz H. Bauschke, Osman Güler, Adrian S. Lewis, Hristo S. Sendov
 9 Feb 2018

Stefan Sremac
"The Lax Conjecture Is True", 2005
by Adrian S. Lewis, Pablo A. Parrilo, Motakuri V. Ramana
 16 Feb 2018

Julian Romero
"Exponential lower bounds on spectrahedral representations of hyperbolicity cones", 2017
by Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz
 23 Feb 2018

Reading Week. This Friday we have no talks.
 2 Mar 2018

Kanstantsin Pashkovich
"On Leonid Gurvits’s Proof for Permanents", 2010
by Monique Laurent and Alexander Schrijver
 9 Mar 2018
(MC 5417)

Sharat Ibrahimpur
"Maximizing Determinants under Partition Constraints", 2015
by Aleksandar Nikolov and Mohit Singh
Here is the talk "Maximizing Subdeterminants and Connections to Permanents and Inequalities on Stable Polynomials" by Mohit Singh.
 16 Mar 2018

Justin Toth
"Nash Social Welfare, Matrix Permanent, and Stable Polynomials", 2016
by Nima Anari, Shayan Oveis Gharan, Amin Saberi and Mohit Singh
Here is the talk "Nash Social Welfare, Matrix Permanent, and Stable Polynomials" by Nima Anari.
 23 Mar 2018

Akshay Ramachadran
"A Generalization of Permanent Inequalities and Applications in Counting and Optimization", 2017
by Nima Anari and Shayan Oveis Gharan
 30 Mar 2018

Good Friday. This Friday we have no talks.