#### 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.

Friday, October 26, 2018 — 3:30 PM EDT

**Title:** Vertex Minors

Speaker: | Jim Geelen |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

I will give an introduction to vertex-minors of graphs. At first sight vertex minors are a bit peculiar but they are closely related to graph minors and possibly even easier to work with.

Friday, October 26, 2018 — 1:00 PM EDT

**Title**:Local Search Guarantees on Facility Location Problems

Speaker: | Zishen Qu |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: We will show that guarantees can be given on algorithms for the k-median problem based on local search heuristics.

Thursday, October 25, 2018 — 3:30 PM EDT

Title: Some problems on the size Ramsey numbers

Speaker: | Gholam Reza Omidi |

Affiliation: | Isfahan University of Technology |

Room: | MC 5417 |

**Abstract**: For given simple graphs $G_1$ and $G_2$, the size Ramsey number $\hat{R}(G_1,G_2)$ is the smallest positive integer $m$,

Thursday, October 25, 2018 — 1:30 PM EDT

**Title**: Maximum Independent Sets in Erdos-Ko-Rado Combinatorics

Speaker: | Nathan Lindzey |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract**: We discuss a general algebraic method for characterizing maximum independent sets in graphs that arise in Erdos-Ko-Rado combinatorics, provided the graphs are large enough.

Friday, October 19, 2018 — 3:30 PM EDT

**Title:** New algorithms for maximum disjoint paths based on tree-likeness

Speaker: | Matthias Mnich |

Affiliation: | University of Bonn |

Room: | MC 5501 |

**Abstract:**

We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph.

Friday, October 19, 2018 — 1:00 PM EDT

**Title**: Primal-dual and Lagrangian relaxation techniques for k-median

Speaker: | Madison Van Dyk |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: We will develop primal-dual algorithms to obtain constant-factor approximations for the uncapacitated facility location problem.

Thursday, October 18, 2018 — 3:30 PM EDT

**Title**: Extending Thomassen’s Theorem to Two Faces

Speaker: | Joshua Nevin |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract**:

Let G be a planar graph and let L be a list-assignment for G in which there is a precolored edge on the outer face, every other vertex on the outer face has a list of size at least 3, and every other vertex in G has a list of size at least 5.

Thursday, October 18, 2018 — 1:30 PM EDT

**Title**: Graphs of Homomorphisms

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract**: If X and Y are graphs and f is a function on V (X) taking values in V (Y ), then the graph of

f is the subset formed by the pairs (x; f(x)) for x in V (X).

Wednesday, October 17, 2018 — 4:00 PM EDT

**Title**: Tutorial on back-propagation and automatic differentiation

Speaker: | Steve Vavasis |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: In this presentation, I'll cover the basics of automatic differentiation (AD).

Wednesday, October 17, 2018 — 3:30 PM EDT

**Title: **Basis Shape Loci and the Positive Grassmannian

Speaker: | Cameron Marcot |

Affiliation: | University of Waterloo |

Room: | MC 6483 |

**Abstract:** We study the set of k-dimensional planes in R^n admitting a basis of vectors with prescribed supports.

Friday, October 12, 2018 — 10:30 AM EDT

**Title:** Offline Assisted Group Key Exchange

Speaker: | Gareth Davies |

Affiliation: | Norwegian University of Science and Technology (NTNU) |

Room: | MC 5417 |

**Abstract:**

This talk will focus on the problem of forward secrecy in group key exchange (GKE), where most of the participants remain offline until they wish to compute the key.

Thursday, October 4, 2018 — 3:30 PM EDT

**Title**: Representable orientable matroids that are not real-representable

Speaker: | Rutger Campbell |

Affiliation: | University of Waterllo |

Room: | MC 5417 |

**Abstract**: In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.

Thursday, October 4, 2018 — 1:30 PM EDT

**Title**: Controllable graphs

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 6486 |

**Abstract**: A graph is controllable if no eigenvector is orthogonal to the all-ones vector.

Wednesday, October 3, 2018 — 4:00 PM EDT

**Title**: Review of martingale theory, stochastic gradient descent, and adaptive line-line-search for stochastic optimization.

Speaker: | Courtney Paquette |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**: With the rise of large data sets, practical algorithms for machine learning often use probability and statistics.

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.