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

Thursday, August 6, 2020 — 2:30 PM EDT

**Title:** Abelian covering graphs and their properties

Speaker: | Olha Silina |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

A covering graph is a structure obtained from a graph by ‘replacing’ every vertex with a coclique of size $r$. The main focus of this talk is connections between (spectral) characteristic of a cover and properties such as being walk- or distance- regular.

Monday, August 3, 2020 — 11:30 AM EDT

**Title:** Decomposing discrete quantum walks into continuous quantum walks

Speaker: | Harmony Zhan |

Affiliation: | York University |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

The Grover walk is a discrete quantum walk inspired by Grover's search algorithm. It takes place on the arcs of a graph, and alternates between "coin flips" and "arc reversal". In this talk, I show that for a distance regular graph X with diameter d and intertible A(X), the Grover walk on X can be "decomposed" into at most d "commuting" continuous quantum walks.

Friday, July 31, 2020 — 3:30 PM EDT

**Title:** Data-Driven Sample-Average Approximation for Stochastic Optimization with Covariate Information

Speaker: | Jim Luedtke |

Affiliation: | University of Wisconsin-Madison |

Zoom: | Please email Emma Watson |

**Abstract:**

We consider optimization models for decision-making in which parameters within the optimization model are uncertain, but predictions of these parameters can be made using available covariate information. We consider a data-driven setting in which we have observations of the uncertain parameters together with concurrently-observed covariates. Given a new covariate observation, the goal is to choose a decision that minimizes the expected cost conditioned on this observation. We investigate a data-driven framework in which the outputs from a machine learning prediction model are directly used to define a stochastic programming sample average approximation (SAA).

Friday, July 31, 2020 — 1:30 PM EDT

**Title:** Weighted Maximum Multicommodity Flows over time

Speaker: | Haripriya Pulyassary |

Affiliation: | University of Waterloo |

Zoom: | Contact Sharat Ibrahimpur |

**Abstract:**

In various applications, flow does not travel instantaneously through a network, and the amount of flow traveling on an edge may vary over time. This temporal dimension is not captured by the classic static network flow models but can be modeled using flows over time.

Thursday, July 30, 2020 — 2:30 PM EDT

**Title****:** P\'olya enumeration theorems in algebraic geometry

Speaker: | Gilyoung Cheong |

Affiliation: | University of Michigan |

Zoom: | Contact Karen Yeats |

**Abstract:**

We will start by comparing Macdonald's formula of the generating function for the symmetric powers of a compact complex manifold and Grothendieck's formula of the zeta series of a projective variety over a finite field, an explicit version of Dwork's rationality result.

Monday, July 27, 2020 — 11:30 AM EDT

**Title:** Continuous Quantum Walks on Graphs

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

A quantum walk is a (rather imperfect analog) of a random walk on a graph. They can be viewed as gadgets that might play a role in quantum computers, and have been used to produce algorithms that outperform corresponding classical procedures.

Friday, July 24, 2020 — 3:30 PM EDT

**Title:** Semidefinite programming representations for separable states

Speaker: | Hamza Fawzi |

Affiliation: | University of Cambridge |

Zoom: | Please email Emma Watson |

**Abstract:**

The set of separable (i.e., non-entangled) bipartite states is a convex set that plays a fundamental role in quantum information theory. The problem of optimizing a linear function on the set of separable states is closely related to polynomial optimization on the sphere. After recalling the sum-of-squares hierarchy for this problem, I will show bounds on the rate of convergence of this SDP hierarchy; and prove that the set of separable states has no SDP representation of finite size.

Friday, July 24, 2020 — 1:30 PM EDT

**Title: **A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case

Speaker: | Sharat Ibrahimpur |

Affiliation: | University of Waterloo |

Zoom: | Contact Sharat Ibrahimpur |

**Abstract:**

Given a connected undirected graph G on n vertices, and non-negative edge costs c, the 2ECM problem is that of finding a 2-edge connected spanning multisubgraph of G of minimum cost. The natural linear program (LP) for 2ECM, which coincides with the subtour LP for the Traveling Salesman Problem on the metric closure of G, gives a lower bound on the optimal cost.

Thursday, July 23, 2020 — 2:30 PM EDT

**Title:** Chord diagrams, colours, and QED

Speaker: | Marcel Golz |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

Feynman graphs in quantum electrodynamics are essentially chord diagrams with photon edges taking the role of chords attached to lines or cycles given by electron edges. The associated Feynman integrals involve traces of Dirac gamma matrices whose computation leads to large sums of scalar Feynman integrals (cf. the earlier talk by O. Schnetz).

Monday, July 20, 2020 — 11:30 AM EDT

**Title:** Group Theory and the Erd\H{o}s-Ko-Rado (EKR) Theorem

Speaker: | Karen Meagher |

Affiliation: | University of Regina |

Zoom: | Contact Soffia Arnadottir |

**Abstract****:**

Group theory can be a key tool in sovling problems in combinatorics; it can provide a clean and effective proofs, and it can give deeper understanding of why certain combinatorial results hold. My research has focused on the famous Erd\H{o}s-Ko-Rado (EKR) theorem.

Friday, July 17, 2020 — 3:30 PM EDT

**Title:** Point Location and Active Learning - Learning Halfspaces Almost Optimally

Speaker: | Shachar Lovett |

Affiliation: | UC San Diego |

Zoom: | Please email Emma Watson |

**Abstract:**

The point location problem is a central problem in computational geometry. It asks, given a known partition of R^d by n hyperplanes, and an unknown input point, to find the cell in the partition to which the input point belongs. The access to the input is via linear queries. A linear query is specified by an hyperplane, and the result of the query is which side of the hyperplane the input point lies in.

Friday, July 17, 2020 — 1:30 PM EDT

**Title:** Two unsolved problems: Birkhoff--von Neumann graphs and PM-compact graphs

Speaker: | Nishad Kothari |

Affiliation: | CSE Department, Indian Institute of Technology Madras |

Zoom: | Contact Sharat Ibrahimpur |

**Abstract:**

A well-studied object in combinatorial optimization is the {\it perfect matching polytope} $\mathcal{PMP}(G)$ of a graph $G$ --- the convex hull of the incidence vectors of all perfect matchings of $G$. A graph $G$ is {\it Birkhoff--von Neumann} if $\mathcal{PMP}(G)$ is characterized solely by non-negativity and degree constraints, and $G$ is {\it PM-compact} if the combinatorial diameter of $\mathcal{PMP}(G)$ equals one.

Thursday, July 16, 2020 — 2:30 PM EDT

**Title:** Dynamics of plane partitions

Speaker: | Oliver Pechenik |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

Consider a plane partition P in an a X b X c box. The rowmotion operator sends P to the plane partition generated by the minimal elements of its complement. We show rowmotion resonates with frequency a+b+c-1, in the sense that each orbit size shares a prime divisor with a+b+c-1. This confirms a 1995 conjecture of Peter Cameron and Dmitri Fon-Der-Flaass. (Based on joint works with Kevin Dilks & Jessica Striker and with Becky Patrias.)

Monday, July 13, 2020 — 11:30 AM EDT

**Title:** On the flip graph on perfect matchings of complete graphs and sign reversal graphs

Speaker: | Sebastian Cioaba |

Affiliation: | University of Delaware |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

In this talk, we study the flip graph on the perfect matchings of a complete graph of even order. We investigate its combinatorial and spectral properties including connections to the signed reversal graph and we improve a previous upper bound on its chromatic number.

Friday, July 10, 2020 — 3:30 PM EDT

**Title:** Symmetries and asymptotics of port-based teleportation

Speaker: | Felix Leditzky |

Affiliation: | University of Waterloo |

Zoom: | Please email Emma Watson |

**Abstract:**

Quantum teleportation is one of the fundamental building blocks of quantum Shannon theory. The original teleportation protocol is an exact protocol and amazingly simple, but it requires a non-trivial correction operation to make it work. Port-based teleportation (PBT) is an approximate variant of teleportation with a simple correction operation that renders the protocol unitarily covariant.

Thursday, July 9, 2020 — 2:30 PM EDT

**Title:** Formulas for Macdonald polynomials arising from the ASEP

Speaker: | Olya Mandelshtam |

Affiliation: | Brown University |

Zoom: | Contact Karen Yeats |

**Abstract:**

The asymmetric simple exclusion process (ASEP) is a one-dimensional model of hopping particles that has been extensively studied in statistical mechanics, probability, and combinatorics. It also has remarkable connections with orthogonal symmetric polynomials in many variables such as Macdonald and Koornwinder polynomials.

Monday, July 6, 2020 — 11:30 AM EDT

**Title:** A covering graph perspective on Huang’s theorem

Speaker: | Maxwell Levit |

Affiliation: | University of Waterloo |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

Just about a year ago, Hao Huang resolved the sensitivity conjecture by proving that any induced subgraph on more than half the vertices of the hypercube $Q_n$ has maximum degree at least $\sqrt(n)$. The key ingredient in his proof is a special $\pm 1$ signing of the adjacency matrix of $Q_n$.

Friday, July 3, 2020 — 3:30 PM EDT

**Title:** Number-theoretic methods in quantum computing

Speaker: | Peter Selinger |

Affiliation: | Dalhousie University |

Zoom: | Please email Emma Watson |

**Abstract:**

An important problem in quantum computing is the so-called \emph{approximate synthesis problem}: to find a quantum circuit, preferably as short as possible, that approximates a given target operation up to given $\epsilon$. For nearly two decades, from 1995 to 2012, the standard solution to this problem was the Solovay-Kitaev algorithm, which is based on geometric ideas. This algorithm produces circuits of size $O(\log^c(1/\epsilon))$, where $c$ is a constant approximately equal to $3.97$. It was a long-standing open problem whether the exponent $c$ could be reduced to $1$.

Thursday, July 2, 2020 — 2:30 PM EDT

**Title:** Factorial Schur Functions and Quantum Intergrability

Speaker: | Timothy Miller |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

I will introduce factorial Schur functions as they relate to my Master's thesis. Factorial Shur functions are a generalization of Schur functions with a second family of "shift" parameters. In 2009, Zinn-Justin reproved the answer to a tiling problem (the puzzle rule) with a toy fermionic model, using techniques from physics to extract the result.

Friday, June 26, 2020 — 3:30 PM EDT

**Title:** Discrete diffusion on graphs and real hyperplane arrangements

Speaker: | David Wagner |

Affiliation: | University of Waterloo |

Zoom: | Please email Emma Watson |

To view the slides: | Click here |

**Abstract:**

In 2016, Duffy, Lidbetter, Messinger, and Nowakowski introduced the following variation of a chip-firing model on a graph. At time zero, there is an integer number of "chips" at each vertex. Time proceeds in discrete steps. At each step, each edge is examined (in parallel) -- one chip is moved from the greater end to the lesser end if the ends are not equal.

Thursday, June 25, 2020 — 2:30 PM EDT

**Title:** 2-Connected Chord Diagrams and Applications in QFT

Speaker: | Ali Mahmoud |

Affiliation: | University of Waterloo |

Zoom: | Contact Karen Yeats |

**Abstract:**

A functional equation for 2-connected chord diagrams is derived, then is used to calculate asymptotic information for the number of 2-connected chord diagrams by means of alien derivatives applied to factorially divergent power series.

Friday, June 19, 2020 — 3:30 PM EDT

**Title:** Widths in even-hole-free graphs

Speaker: | Nicolas Trotignon |

Affiliation: | CNRS - LIP - École Normale Supérieure de Lyon |

Zoom: | Please email Emma Watson |

**Abstract:**

Historically, the study of even-hole-free graphs is motivated by the analogy with perfect graphs. The decomposition theorems that are known for even-hole-free graphs are seemingly more powerful than the ones for perfect graphs: the basic classes and the decompositions are in some respect more restricted. But strangely, in an algorithmic perpective, much more is known for perfect graphs.

Thursday, June 18, 2020 — 2:30 PM EDT

**Title:** Sandpiles and representation theory

Speaker: | Victor Reiner |

Affiliation: | University of Minnesota |

Zoom: | Contact Karen Yeats |

**Abstract:**

For an undirected graph, its sandpile group is an interesting isomorphism invariant-- it is a finite abelian group that describes the integer cokernel of the graph's Laplacian matrix.

Thursday, June 18, 2020 — 1:03 PM EDT

**Title: **Graph coloring of graphs with large girth is hard for the Nullstellensatz

Speaker: | Julián Romero |

Affiliation: | University of Waterloo |

Zoom: | Contact Sharat Ibrahimpur |

**Abstract:**

In this talk we will discuss a method to solve combinatorial problems using hierarchies of systems of linear equations using Hilbert's Nullstellensatz. In particular, we will study the behaviour of these hierarchies for deciding the non-$k$-colorabilty of graphs.

Friday, June 12, 2020 — 3:30 PM EDT

**Title:** Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis

Speaker: | Courtney Paquette |

Affiliation: | University of Waterloo |

Zoom: | Please email Emma Watson |

**Abstract:**

Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. One difficulty is that the analysis can depend on the probability distribution of the inputs to the model.

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.