Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, ext 33038
PDF files require Adobe Acrobat Reader.
Visit our COVID19 information website to learn how Warriors protect Warriors.
Please note: The University of Waterloo is closed for all events until further notice.
Sun  Mon  Tue  Wed  Thu  Fri  Sat 

28

29

30

1

4








5

7

8

11







12

14

15

18







19

21

22

25







26

28

29

1






Title: Factorial Schur Functions and Quantum Intergrability
Speaker: Timothy Miller Affiliation: University of Waterloo Zoom: Contact Karen YeatsAbstract:
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, ZinnJustin reproved the answer to a tiling problem (the puzzle rule) with a toy fermionic model, using techniques from physics to extract the result.
Title: Numbertheoretic methods in quantum computing
Speaker: Peter Selinger Affiliation: Dalhousie University Zoom: Please email Emma WatsonAbstract:
An important problem in quantum computing is the socalled \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 SolovayKitaev 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 longstanding open problem whether the exponent $c$ could be reduced to $1$.
Title: A covering graph perspective on Huang’s theorem
Speaker: Maxwell Levit Affiliation: University of Waterloo Zoom: Contact Soffia ArnadottirAbstract:
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$.
Title: Formulas for Macdonald polynomials arising from the ASEP
Speaker: Olya Mandelshtam Affiliation: Brown University Zoom: Contact Karen YeatsAbstract:
The asymmetric simple exclusion process (ASEP) is a onedimensional 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.
Title: Symmetries and asymptotics of portbased teleportation
Speaker: Felix Leditzky Affiliation: University of Waterloo Zoom: Please email Emma WatsonAbstract:
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 nontrivial correction operation to make it work. Portbased teleportation (PBT) is an approximate variant of teleportation with a simple correction operation that renders the protocol unitarily covariant.
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 ArnadottirAbstract:
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.
Title: Dynamics of plane partitions
Speaker: Oliver Pechenik Affiliation: University of Waterloo Zoom: Contact Karen YeatsAbstract:
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+c1, in the sense that each orbit size shares a prime divisor with a+b+c1. This confirms a 1995 conjecture of Peter Cameron and Dmitri FonDerFlaass. (Based on joint works with Kevin Dilks & Jessica Striker and with Becky Patrias.)
Title: Two unsolved problems: Birkhoffvon Neumann graphs and PMcompact graphs
Speaker: Nishad Kothari Affiliation: CSE Department, Indian Institute of Technology Madras Zoom: Contact Sharat IbrahimpurAbstract:
A wellstudied 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 Birkhoffvon Neumann} if $\mathcal{PMP}(G)$ is characterized solely by nonnegativity and degree constraints, and $G$ is {\it PMcompact} if the combinatorial diameter of $\mathcal{PMP}(G)$ equals one.
Title: Point Location and Active Learning  Learning Halfspaces Almost Optimally
Speaker: Shachar Lovett Affiliation: UC San Diego Zoom: Please email Emma WatsonAbstract:
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.
Title: Group Theory and the Erd\H{o}sKoRado (EKR) Theorem
Speaker: Karen Meagher Affiliation: University of Regina Zoom: Contact Soffia ArnadottirAbstract:
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}sKoRado (EKR) theorem.
Title: Chord diagrams, colours, and QED
Speaker: Marcel Golz Affiliation: University of Waterloo Zoom: Contact Karen YeatsAbstract:
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).
Title: A 4/3Approximation Algorithm for the Minimum 2Edge Connected Multisubgraph Problem in the HalfIntegral Case
Speaker: Sharat Ibrahimpur Affiliation: University of Waterloo Zoom: Contact Sharat IbrahimpurAbstract:
Given a connected undirected graph G on n vertices, and nonnegative edge costs c, the 2ECM problem is that of finding a 2edge 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.
Title: Semidefinite programming representations for separable states
Speaker: Hamza Fawzi Affiliation: University of Cambridge Zoom: Please email Emma WatsonAbstract:
The set of separable (i.e., nonentangled) 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 sumofsquares 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.
Title: Continuous Quantum Walks on Graphs
Speaker: Chris Godsil Affiliation: University of Waterloo Zoom: Contact Soffia ArnadottirAbstract:
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.
Title: P\'olya enumeration theorems in algebraic geometry
Speaker: Gilyoung Cheong Affiliation: University of Michigan Zoom: Contact Karen YeatsAbstract:
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.
Title: Weighted Maximum Multicommodity Flows over time
Speaker: Haripriya Pulyassary Affiliation: University of Waterloo Zoom: Contact Sharat IbrahimpurAbstract:
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.
Title: DataDriven SampleAverage Approximation for Stochastic Optimization with Covariate Information
Speaker: Jim Luedtke Affiliation: University of WisconsinMadison Zoom: Please email Emma WatsonAbstract:
We consider optimization models for decisionmaking in which parameters within the optimization model are uncertain, but predictions of these parameters can be made using available covariate information. We consider a datadriven setting in which we have observations of the uncertain parameters together with concurrentlyobserved 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 datadriven framework in which the outputs from a machine learning prediction model are directly used to define a stochastic programming sample average approximation (SAA).
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, ext 33038
PDF files require Adobe Acrobat Reader.
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.