Please email any errors or updates to our website support/editor.

PDF files require Adobe Acrobat Reader.

Visit our **COVID-19 Information website** for information on our response to the pandemic.

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

Every Wednesday 2:30 pm - 4:oo pm on Zoom.

Virtual Coffee Break held before at 2:15 pm.

Graduate students, faculty members, and guests. The last few weeks of seminars will be presentations from the URA students themselves.

Faculty members and URA students will receive an email before each seminar with the Zoom meeting information. If you wish to join the seminar and did not recieve an email, please contact Faculty Coordinator Douglas Stebila for the Zoom information.

Speaker: | Jane Gao |

Affiliation: | University of Waterloo |

Title: Hamilton cycles in random graphs

Abstract: Determining if a graph is Hamiltonian is NP-complete. Finding sufficient conditions for the existence of Hamilton cycles is one of the most classical problems in both theoretical computer science and combinatorics. In this talk we discuss this problem in random graphs. We will discuss when do Hamilton cycles appear, and when they appear, how to find one efficiently.

Speaker: | Douglas Stebila |

Affiliation: | University of Waterloo |

Title: Lattice-based post-quantum cryptography

Abstract: Lattice-based cryptography is one of the most promising candidates for efficient quantum-resistant cryptography. In this talk, I'll present the motivation for post-quantum cryptography, introduce the learning with errors problem and how it relates to lattices, and give an overview of the work going on at the University of Waterloo in post-quantum cryptography.

Speaker: | Nina Bindel |

Affiliation: | University of Waterloo |

Title: Lattice-based Cryptography - an Example for Quantum-Secure Cryptography

Abstract: Most common cryptographic protocols such as RSA and ECC will become insecure once a sufficiently large fault-tolerant quantum computer is built with the capability to run Shors quantum algorithm and its variants. To address this security threat, cryptographers have been working on alternative algorithms which are not known to be vulnerable to attacks using quantum computers -- the so-called post-quantum or quantum-safe cryptographic algorithms. In order to advance this effort, NIST launched a new standardization process with the goal of selecting the next generation of quantum-safe public-key cryptographic algorithms in 2017.

In this talk we will introduce one class of presumably quantum-secure algorithms, namely lattice-based cryptographic algorithms. To this end, we first give the definition of lattices and mathematical hard lattice problems. Afterwards, we present a modern lattice-based encryption scheme and discuss its security guarantees.

Speaker: | Kevin Purbhoo |

Affiliation: | University of Waterloo |

Title: Points, lines, planes, and power series

Abstract: In combinatorics we often want to answer enumerative questions about discrete objects, e.g. how many trees on 5 vertices? In geometry, one can ask questions of a similar flavour, e.g. how many conics through 5 general points in the plane? Both of these questions are about determining the cardinality of some finite set, but there is an important difference. With a combinatorial question, you could in principle obtain the answer with no machinery whatsoever, by simply listing all of the possibilities and literally counting. With a geometry question, the most naive approach is usually to solve some big system of equations.

Some of the most fundamental enumerative geometry questions are about simple linear spaces: points, lines and planes. In the late 19th century, H. Schubert developed a "calculus" for solving such problems, in which one essentially transforms the geometry problem into a discrete combinatorial problem. In this talk, I'll explain one can use formal power series to bridge the gap between the geometric and discrete worlds.

Speaker: | Joshua Nevin |

Affiliation: | University of Waterloo |

Title: Coloring graphs from Many Palettes

Abstract: Given a graph G, the graph coloring problem asks how many colors are needed in order to assign every vertex of G a color such that every color class of V(G) is an independent set. In this talk, we introduce a natural generalization of graph coloring called list-coloring, in which every vertex is allowed to have its own palette of colors. Many results about ordinary graph coloring have natural generalizations to the setting of list-coloring. Some of them even have easier proofs in this more general setting.

Speaker: | Ricardo Fukasawa |

Affiliation: | University of Waterloo |

Title: The vehicle routing problem with uncertain demands

Abstract: Deterministic optimization problems typically consider that all data is given as an input which is known a priori. While that assumption has allowed multiple optimization methods to be developed, in practice that assumption often does not hold. Thus, researchers have been considering how to optimize problems when some of the data is considered as an unknown quantity, for which only limited information is available.

In this talk, I will use the vehicle routing problem to introduce several different approaches on how to deal with uncertainty of the data, by presenting approaches for the vehicle routing problem with uncertain demands. I will show challenges that arise when attempting to study the problem depending on the choice of how to deal with uncertain data.

Speaker: | Luke Schaeffer |

Affiliation: | University of Waterloo |

Title: The vehicle routing problem with uncertain demands

Abstract: A general quantum circuit can be simulated in exponential time on a classical computer. However, if the circuit has a planar layout, then Markov and Shi showed how to do much better with an algorithm that is exponential in the treewidth of the underlying graph. Separately, Gottesman-Knill showed that if all gates in a quantum circuit are restricted to be Clifford, then there is a polynomial time simulation. We combine these two results and show how treewidth and planarity can be used to improve Clifford circuit simulation. Joint work with David Gosset, Daniel Grier, Alex Kerzner.

Speaker: | Walaa Moursi |

Affiliation: | University of Waterloo |

Title: An invitation to monotone operators and their applications in optimization

The Matching Augmentation Problem: A 5/3 - Approximation Algorithm

Searching Excluded Minors of GF(5)-Representable Matroids

Speaker: | Robert Cummings |

Affiliation: | University of Waterloo |

Title: The Matching Augmentation Problem: A 5/3 - Approximation Algorithm

Abstract: We present a 5/3 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost.

Speaker: | Timothy Wahyudi |

Affiliation: | University of Waterloo |

Title: Searching Excluded Minors of GF(5)-Representable Matroids

omega-Condition Number and Application to Quasi-Newton Methods

Hessian curves and 3-isogenies

Attacks on RLWE Key Exchange with Reused Keys

Speaker: | Matt (Chong Rong) Dong |

Affiliation: | University of Waterloo |

Title: omega-Condition Number and Application to Quasi-Newton Methods

Abstract: The standard matrix condition number has been widely studied in numerical computing. In this presentation, we define an alternative matrix condition number, the omega-Condition Number, and look into his applications to Quasi-Newton methods.

Speaker: | Vincent Macri |

Affiliation: | University of Waterloo |

Title: Hessian curves and 3-isogenies

Abstract: We analyze it recent results on arithmetic and isogeny computations on twisted Hessian curves can be used to improve the speed of the SIKE cryptosystem over the currently used Montgomery curves.

Speaker: | Shannon Veitch |

Affiliation: | University of Waterloo |

Title: Attacks on RLWE Key Exchange with Reused Keys

Abstract: Key exchange protocols which allow for key reuse can reduce storage requirements and increase efficiency. Thus, researchers have been considering how to construct lattice-based key exchange protocols with reusable keys. In this talk, I'll present some lattice-based key exchange protocols and corresponding attacks which take advantage of reused keys.

Weighted Maximum Multicommodity Flows over Time

Random graphs with specified degrees

Counting C_2 invariant on the circulant family of graphs

Speaker: | Priya Pulyassary |

Affiliation: | University of Waterloo |

Title: Weighted Maximum Multicommodity Flows over Time

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. In this talk, we will introduce flows over time and present the technique of Delta-condensed networks (which was first introduced by Fleischer and Skutella). We will also present our current work on the weighted maximum multicommodity flows over time problem. This is joint work with Jochen Koenemann and Madison Van Dyk.

Speaker: | Yuval Ohapkin |

Affiliation: | University of Waterloo |

Title: Random graphs with specified degrees

Abstract: Given a graphical degree sequence $d = (d_1,...,d_n)$, let $G(n, d)$ denote a uniformly random graph on vertex set $[n]$ where vertex $i$ has degree $d_i$. We introduce a combinatorial tool to give upper and lower bounds on the joint probability of an arbitrary set of edges in $G(n, d)$, with an application to a paper by Alan Frieze, Michael Krivelevich, and Cliff Smyth on the chromatic number of $G(n, d)$.

Speaker: | Mushegh Shahinyan |

Affiliation: | University of Waterloo |

Title: Counting C_2 invariant on the circulant family of graphs

Abstract: The arithmetic invariant on Feynman Diagrams (Graphs) called the "C_2 invariant" is a useful tool for detecting properties of Feynman Integrals. We present this identity on graphs from a purely combinatorial perspective and go over some results and strategies for computing it for circulant graphs.

Approximation Algorithms for 2-Node Connectivity

Subdivergence-Free Gluings of Trees

Distance regular covers of complete graphs

Speaker: | Jasper Zhu |

Affiliation: | University of Waterloo |

Title: Approximation Algorithms for 2-Node Connectivity

Abstract: An important problem in network connectivity is finding an edge-minimal 2-node connected spanning subgraph (2NCSS). Previously, Santosh Vempala and Adrian Vetta claimed to have achieved a 4/3 approximation algorithm to this problem, but a counterexample was later found by Klaus Heeger and Jens Vygen.

Speaker: | Jordan Long |

Affiliation: | University of Waterloo |

Title: Subdivergence-Free Gluings of Trees

Abstract: Motivated by questions in quantum field theory, we introduce a purely combinatorial problem of counting subdivergence-free gluings of trees. We present closed-form expressions counting subdivergence-free gluings for four different families of trees, as well as an algorithm to count subdivergence-free gluings of arbitrary pairs of trees. This is joint work with Clair Dai and Karen Yeats.

Speaker: | Olha Silina |

Affiliation: | University of Waterloo |

Title: Distance regular covers of complete graphs

Abstract: A cover is a structure obtained from a graph by 'replacing' every vertex with a coclique of fixed size(following certain rules and subject to some parameters). In this talk, I am going to look at the covers of complete graphs that are distance regular. In particular, I will give necessary conditions on these parameters for the cover to exist.

Speaker: | Donny Cheung |

Affiliation: |

Abstract: Donny Cheung is a Technical Lead/Manager for Healthcare & Life Sciences AI for Google Cloud. Donny completed his PhD in quantum computing from UW's department of Combinatorics and Optimization. He'll discuss what he does at Google and he how got there.

Faculty of Mathematics *Web*Notice notices

Fields Institute: upcoming lecture series

Fields Institute: upcoming workshops

The Matroid Union: online talks

E-NLA: Online seminar series on Numerical Linear Algebra

Please email any errors or updates to our website support/editor.

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