#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Thursday, September 30, 2021 1:00 PM EDT

**Title: **Forcing Quasirandomness in Permutations

Speaker: | John Noel |

Affiliation: | University of Victoria |

Zoom: | Contact Steve Melczer |

**Abstract:**

A striking result in graph theory is that the property of a graph being quasirandom (i.e. resembling a random graph) is characterized by the number of edges and the number of 4-cycles being close to the expected number in a random graph. Král’ and Pikhurko (2013) proved an analogous result for permutations; i.e. that quasirandom permutations are characterized by the densities of all permutations of length 4.

Thursday, September 30, 2021 11:00 AM EDT

**Title:** Structured (In)Feasibility: Nonmonotone Operator Splitting in Nonlinear Spaces

Speaker: | Bissan Ghaddar |

Affiliation: | Western University |

Zoom: | Register through The Fields Institute |

**Abstract:**

Several challenging optimization problems in power networks involve operational decisions, non-linear models of the underlying physics described by the network as well as uncertainty in the system parameters. However, these networks exhibit a nice structure. This talk provides an overview of approaches that combine recent advances in robust optimization and conic relaxations of polynomial optimization problems along with exploiting the structure of the underlying problem. These approaches are demonstrated on applications arising in power networks.

Thursday, September 30, 2021 10:00 AM EDT

**Title:** Semidefinite Optimization Approaches for Reactive Optimal Power Flow Problems

Speaker: | Miguel Anjos |

Affiliation: | University of Edinburgh |

Zoom: | Register through The Fields Institute |

**Abstract:**

The Reactive Optimal Power Flow (ROPF) problem consists in computing an optimal power generation dispatch for an alternating current transmission network that respects power flow equations and operational constraints. Some means of voltage control are modelled in ROPF such as the possible activation of shunts, and these controls are modelled using discrete variables. The ROPF problem belongs to the class of nonconvex MINLPs, which are NP-hard problems. We consider semidefinite optimization approaches for solving ROPF problems and their integration into a branch-and-bound algorithm.

Monday, September 27, 2021 11:30 AM EDT

**Title:** Graph Continued Fractions

Speaker: | Thomás Spier |

Affiliation: | Matemática Pura e Aplicada (IMPA) |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

This talk is about a connection between matching polynomials and continued fractions. For the matching polynomials: we prove a refinement of a theorem by Ku and Wong, which extends the classical Gallai-Edmonds decomposition;

Friday, September 24, 2021 3:30 PM EDT

**Title:** Tightly-Secure Digital Signatures

Speaker: | Tibor Jager |

Affiliation: | University of Wuppertal, Germany |

Zoom: | Please email Emma Watson |

**Abstract:**

This talk will cover two recent results on tightly-secure digital signature schemes from PKC 2021 and ASIACRYPT 2021.

The first part will consider a strong multi-user security definition for signatures with adaptive corruptions of secret keys, discuss its applications, and the technical challenges of constructing signatures with tight security in this setting. Then we will show a quite simple and efficient construction, based on sequential OR-proofs.

Monday, September 20, 2021 11:03 AM EDT

**Title:** Spectral Properties of the exponential distance matrix

Speaker: | Kate Lorenzen |

Affiliation: | Linfield University |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

Given a graph $G$, the exponential distance matrix is defined entry-wise by letting the $(u,v)$-entry be $q^{dist(u,v)}$ where $dist(u,v)$ is the distance between the vertices $u$ and $v$ with the convention that if vertices are in different components, then $q^{dist(u,v)}=0$. We establish several properties of the characteristic polynomial (spectrum) for this matrix and the inertia of some graph families.

Friday, September 17, 2021 3:30 PM EDT

**Title:** Approximation Algorithms for Matchings in Big Graphs

Speaker: | Alex Pothen |

Affiliation: | Purdue University |

Zoom: | Please email Emma Watson |

**Abstract:**

Matchings in graphs are classical problems in combinatorial optimization and computer science, significant due to their theoretical importance and relevance to applications. Polynomial time algorithms for several variant matching problems with linear objective functions have been known for fifty years, with important contributions from Tutte, Edmonds, Cunningham, and Pulleyblank (all with Waterloo associations), and they are discussed in the textbook literature.

Monday, September 13, 2021 11:30 AM EDT

**Title:** Tails and Chains

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Zoom: | Contact Soffia Arnadottir |

**Abstract:**

Physicists are interested in "graphs with tails"; these are constructed by choosing a graph X and a subset C of its vertices, then attaching a path of length n to each vertex in C. We ask what is the spectrum of such graph? What happen if n increases? We will see that the answer reduces to questions about the matrix

\[ M(\zeta) := (\zeta_\zeta^{-1})I - A -\zeta D \]

where D is the diagonal 01-matrix with D_{i,i}=1 if i is in C.

Friday, September 10, 2021 3:30 PM EDT

**Title:** On solving bilevel programming problems

Speaker: | Jane Ye |

Affiliation: | University of Victoria |

Zoom: | Please email Emma Watson |

**Abstract:**

A bilevel programming problem is a sequence of two optimization problems where the constraint region of the upper level problem is determined implicitly by the solution set to the lower level problem. It can be used to model a two-level hierarchical system where the two decision makers have different objectives and make their decisions on different levels of hierarchy. Recently more and more applications including those in machine learning have been modelled as bilevel optimization problems. In this talk, I will report some recent developments in optimality conditions and numerical algorithms for solving this class of very difficult optimization problems.

Thursday, September 9, 2021 11:00 AM EDT

**Title:** Structured (In)Feasibility: Nonmonotone Operator Splitting in Nonlinear Spaces

Speaker: | Russell Luke |

Affiliation: | University of Goettingen |

Zoom: | Register through The Fields Institute |

**Abstract:**

The success of operator splitting techniques for convex optimization has led to an explosion of methods for solving large-scale and nonconvex optimization problems via convex relaxation. This success is at the cost of overlooking direct approaches to operator splitting that embrace some of the more inconvenient aspects of many model problems, namely nonconvexity, nonsmoothness, and infeasibility.

Thursday, September 9, 2021 10:00 AM EDT

**Title:** Factorization of completely positive matrices using iterative projected gradient steps

Speaker: | Radu Ioan Bot |

Affiliation: | University of Vienna |

Zoom: | Register through The Fields Institute |

**Abstract:**

We aim to factorize a completely positive matrix by using an optimization approach which consists in the minimization of a nonconvex smooth function over a convex and compact set. To solve this problem we propose a projected gradient algorithm with parameters that take into account the effects of relaxation and inertia. Both projection and gradient steps are simple in the sense that they have explicit formulas and do not require inner loops. We show that the sequence of generated iterates

Friday, September 3, 2021 3:30 PM EDT

**Title:** Chromatic structure in locally sparse graphs

Speaker: | Ross Kang |

Affiliation: | Radboud University Nijmegen |

Zoom: | Please email Emma Watson |

**Abstract:**

Efforts to understand the structure of triangle-free graphs have long played a central role in the development of combinatorial mathematics. Classic results of Mantel (1907), Ramsey (1930), Blanche Descartes (1948) produce global structure from the local property of having no edges in any neighbourhood. Despite the scrutiny it has sustained over the decades, study of this topic, and its close relatives, continues to uncover surprisingly basic challenges, insights and connections. I will give a brief overview of the history as well as the focus of current/recent momentum.

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 co-ordinated within our Office of Indigenous Relations.