#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Visit our COVID-19 information website to learn how Warriors protect Warriors.

Please note: The University of Waterloo is closed for all events until further notice.

Wednesday, December 13, 2017 — 4:00 PM EST

**Title:** Generalized Conditional Gradient for Sparse Estimation

Speaker: | Yaoliang Yu |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

We will be discussing the paper (bearing the same title) of Yaoliang Yu, Xinhua Zhang, and Dale Schuurmans. Structured sparsity is an important modelling tool that expands the applicability of convex formulations for data analysis, however it also creates significant challenges for efficient algorithm design.

Thursday, December 7, 2017 — 3:30 PM EST

**Title:** Continuous Quantum Walks and Symmetric Powers

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract:**

The k-th symmetric power of a graph X has the k-subsets of V(X) as its vertices, and two k-subsets are adjacent if their symmetric difference is an edge in X. A continuous quantum walk on a graph gives rise in a natural walk to walks on it symmetric powers.

Wednesday, December 6, 2017 — 4:00 PM EST

**Title:** Signal Recovery by Proximal Forward-Backward Splitting

Speaker: | Shenghao Yang |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

We will be discussing the paper (bearing the same title) of Patrick Combettes and Valérie Wajs. We show that various inverse problems in signal recovery can be formulated as the generic problem of minimizing the sum of two convex functions with certain regularity properties.

Friday, December 1, 2017 — 3:30 PM EST

**Title:** Turan problems for matroids

Speaker: | Peter Nelson |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

Given a fixed simple binary matroid N, what is the maximum size of a simple rank-r binary matroid that does not contain N a restriction?

Thursday, November 30, 2017 — 3:30 PM EST

**Title:** Asymmetric Latin squares, Steiner triple systems, and 1-factorizations

Speaker: | Nathan Lindzey |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract:**

We outline how the Van der Waerden permanent theorem can be used to show that almost all Latin squares, Steiner triple systems, and 1-factorizations of the complete graph admit only trivial automorphisms.

Thursday, November 30, 2017 — 3:30 PM EST

**Title:** Fragility and circuit-hyperplane relaxation

Speaker: | Jim Geelen |

Affiliation: | University of Waterloo |

Room : | MC 5479 |

**Abstract:**

I will briefly discuss the problem of trying to determine the excluded minors for the class of GF(5)-representable matroids, highlighting the roles of N-fragility and of circuit-hyperplane relaxations.

Wednesday, November 29, 2017 — 4:00 PM EST

**Title:** Efficient First-Order Methods for Linear Programming and Semidefinite Programming

Speaker: | Leanne Stuive |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

We will be discussing the paper (bearing the same title) of James Reneger. We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable.

Friday, November 24, 2017 — 3:30 PM EST

**Title:** Nash-Williams

Speaker: | Joseph Cheriyan |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

Crispin Nash-Williams was one of the founding professors of C&O. The talk will cover a small sample of his mathematical work, and also his association with C&O.

Thursday, November 23, 2017 — 3:30 PM EST

**Title:** Ramsey theory for biased graphs

Speaker: | Peter Nelson |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

We discuss the unavoidable subgraphs of biased graphs whose underlying graph is a clique.

Thursday, November 23, 2017 — 1:30 PM EST

**Title:** Orientations, Pseudoforests, Flows, and the Densest Subgraph

Speaker: | Markus Blumenstock |

Affiliation: | University of Mainz, Germany |

Room: | MC 6486 |

**Abstract:**

Given an undirected graph, consider the problem of finding an orientation such that the max-imum indegree is minimized. The Gabow-Westermann algorithm can solve it by exploiting the matroid structure of pseudoforests.

Wednesday, November 22, 2017 — 4:30 PM EST

**Title:** Sum-of-Squares Proofs in Optimization

Speaker: | Mehdi Karimi |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

The old concept of sum-of-squares found its way into optimization and even machine learning. I will talk about this quickly evolving research area known as convex algebraic geometry.

Wednesday, November 22, 2017 — 4:00 PM EST

**Title:** Alternating Direction Method of Multipliers for the SDP Relaxation of the Quadratic Assignment Problem

Speaker: | Henry Wolkowicz |

Affiliation: | University of waterloo |

Room: | MC 5479 |

**Abstract:**

The semidefinite programming (SDP) relaxation has proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem (QAP), arguably one of the hardest NP-hard discrete optimization problems.

Friday, November 17, 2017 — 3:30 PM EST

**Title:** Recent Advances in Frank-Wolfe Optimization

Speaker: | Simon Lacoste-Julien |

Affiliation: | University of Montreal |

Room: | MC 5501 |

**Abstract:**

The Frank-Wolfe (FW) optimization algorithm has lately re-gained popularity thanks in particular to its ability to nicely handle the structured constraints appearing in machine learning and signal processing applications. However, its convergence rate is known to be slow (sublinear) when the solution lies at the boundary.

Thursday, November 16, 2017 — 3:30 PM EST

**Title:** Constructing cospectral graphs with a different switching

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract:**

Many years ago, Brendan McKay and I introduced a construction of pairs of cospectral graphs, sometimes known as local switching. In the same paper we introduced a second switching technique which produces, as special cases, the smallest pair of cospectral graphs and the smallest pair of connected cospectral graphs.

Thursday, November 16, 2017 — 3:30 PM EST

**Title:** Convex drawings of complete graphs: topology meets geometry

Speaker: | Bruce Richter |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

A drawing D of the complete graph K(n) is the sphere is characterized by, for each isomorph J of K(5), D[J] is homeomorphic to one of the three rectilinear drawings of K(5). Every drawing of K(n) in the plane with all edges straight-line segments is obviously convex. Thus, convex drawings generalize planar point sets that are in general position.

Wednesday, November 15, 2017 — 4:00 PM EST

**Title:** Proximal alternating linearized minimization for nonconvex and nonsmooth problems

Speaker: | Stefan Sremac |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

We will be discussing the paper (having the same title) by Jerome Bolte, Shoham Sabach and Marc Teboulle. We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmooth minimization problems.

Friday, November 10, 2017 — 3:30 PM EST

**Title:** Coloring (cap even hole)-free graphs

Speaker: | Shenwei Huang |

Affiliation: | Wilfrid Laurier University |

Room: | MC 5501 |

**Abstract:**

An even cycle of length 4 or more is called an even hole. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this talk we consider (cap, even hole)-free graphs, i.e., graphs that do not contain any even hole or cap as an induced subgraph.

Thursday, November 9, 2017 — 3:30 PM EST

**Title:** An Introduction to Discrete Quantum Walks

Speaker: | Harmony Zhan |

Affiliation: | University of waterloo |

Room: | MC 6486 |

**Abstract:**

Thursday, November 9, 2017 — 3:30 PM EST

**Title:** An application of graph "recolouring”

Speaker: | Ben Moore |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

I will prove that for any graph G, if there is an edge e such that G-e has less than (k-1)!/2 cycles of length zero mod k, then the chromatic number of G is less or equal to k.

Wednesday, November 8, 2017 — 4:00 PM EST

**Title:** A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

Speaker: | Nargiz Kalantarova |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

We will be discussing the paper (having the same title) by Amir Beck and Marc Teboulle. We consider the class of iterative shrinkage-thresholding algorithms (ISTA) for solving linear inverse problems arising in signal/image processing. This class of methods, which can be viewed as an extension of the classical gradient algorithm, is attractive due to its simplicity and thus is adequate for solving large-scale problems even with dense matrix data.

Friday, November 3, 2017 — 3:30 PM EDT

**Title:** How we solve linear programs

Speaker: | Laurent Poirrier |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

Linear programming is one of the most fundamental tools in optimization, and its theoretical complexity is well understood. In practice though, things are quite different: Which types of problems can we really solve? What sizes? With what algorithms?

Thursday, November 2, 2017 — 3:30 PM EDT

**Title:** A short proof of a forgotten result

Speaker: | Bertrand Guenin |

Affiliation: | University of Waterloo |

Room: | MC 4042 |

**Abstract:**

Wednesday, November 1, 2017 — 4:00 PM EDT

**Title:** A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets

Speaker: | Ryan Kinnear |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

We will be discussing the paper (having the same title) by Roux, Schmidt, and Bach. The authors propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex.

Friday, October 27, 2017 — 3:30 PM EDT

**Title: **Some matrix problems in quantum information science

Speaker: | Chi-Kwong Li |

Affiliation: | College of William and Mary, IQC |

Room: | MC 5501 |

**Abstract:**

In this talk, we present some matrix results and techniques in solving certain optimization problems arising in quantum information science.

No quantum mechanics background is required.

Thursday, October 26, 2017 — 3:30 PM EDT

**Title:** Progress on Continuous Quantum Walks

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Roon: | MC 6486 |

**Abstract:**

I will discuss the progress we’ve made in our work on continuous walks. I will start with old stuff (last November) and continue on to current stuff (this week).

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Indigenous Initiatives Office.