Events

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Monday, June 19, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

C&O Reading Group - Nathan Benedetto Proenca

Title: A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut Covering Problem

Speaker: Nathan Benedetto Proenca
Affiliation: University of Waterloo
Location: MC 6029

Abstract:

A cut in a graph \(G = (V, E)\) is a set of edges which has precisely one endpoint in \(S\), for a given subset \(S\) of \(V\). The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. We define a semidefinite programming relaxation of fractional cut covering whose approximate optimal solutions may be rounded into a fractional cut cover via a randomized algorithm.

Monday, June 19, 2023 2:30 pm - 2:30 pm EDT (GMT -04:00)

URA Seminar - Walaa Moursi

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

Speaker: Walaa Moursi
Affiliation: University of Waterloo
Location: MC 5479

Abstract: In this talk, I give an overview of the theory of monotone operators and its connection to optimization algorithms. This talk is a good introduction to how abstract theoretical results serve as bases for successful algorithms in practice.  

Thursday, June 22, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

Algebraic Combinatorics - Karen Yeats

Title: Poset subHopf algebras from growth models in causal set theory and quantum field theory

Speaker: Karen Yeats
Affiliation: University of Waterloo
Location: MC 5501 and Zoom - please contact Oliver Pechenik for the Zoom link

Abstract: In a story some of you have heard from me before, we get subHopf algebras of the Connes-Kreimer Hopf algebra of rooted trees from certain simple tree classes which correspond to solutions to combinatorial analogues of Dyson-Schwinger equations in quantum field theory.  Another important subHopf algebra of the Connes-Kreimer Hopf algebra is the Connes-Moscovici Hopf algebra which can be viewed as coming from rooted trees grown by adding leaves.

Friday, June 23, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

C&O Special Seminar - Noela Müller

Title: The rank of sparse symmetric matrices over arbitrary fields

Speaker: Noela Müller
Affiliation: TU/e Eindhoven University of Technology
Location: MC 5501

Abstract: Consider a sequence of sparse Erdös-Rényi random graphs (G_{n,d/n})_n on n vertices with edge probability d/n. Moreover, we equip the edges of G_{n,d/n} with prescribed non-zero edge weights chosen from an arbitrary field F.

Monday, June 26, 2023 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory - Karen Yeats

Title: Diagonal coefficients of Kirchhoff polynomials of 2k-regular graphs and the proof of the c_2 completion conjecture

Speaker: Karen Yeats
Affiliation: University of Waterloo and Perimeter Institute
Location: Please contact Sabrina Lato for Zoom link

Abstract: I have for many years been interested in graph invariants with the same symmetries as the Feynman period. Recently Erik Panzer found a new such invariant coming from a particular coefficient of the Martin polynomial. Together we used this to prove an over 10 year old conjecture on an arithmetic graph invariant known as the c_2 invariant, and came to understand that diagonal coefficients of Kirchhoff polynomials tie together many of the known graph invariants with the symmetries of Feynman periods and unlock previously inaccessible proofs.

Joint work with Erik Panzer.

Monday, June 26, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

C&O Reading Group - Nathan Benedetto Proenca

Title: A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut Covering Problem, Part II

Speaker: Nathan Benedetto Proenca
Affiliation: University of Waterloo
Location: MC 6029

Abstract: A cut in a graph \(G = (V, E)\) is a set of edges which has precisely one endpoint in \(S\), for a given subset \(S\) of \(V\). The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. We define a semidefinite programming relaxation of fractional cut covering whose approximate optimal solutions may be rounded into a fractional cut cover via a randomized algorithm.

Monday, June 26, 2023 2:30 pm - 2:30 pm EDT (GMT -04:00)

URA Seminar - Jeremy Chizewer

Title: Restricted Intersections and the Sunflower Problem

Speaker: Jeremy Chizewer
Affiliation: University of Waterloo
Location: MC 5479

Abstract: A sunflower with $r$ petals is a collection of $r$ sets over a ground set $X$ such that every element in $X$ is in no set, every set, or exactly one set. Erdos and Rado showed that a family of sets of size $n$ contains a sunflower if there are more than $n!(r-1)^n$ sets in the family. Alweiss et al. and subsequently Rao improved this bound to $(O(r \log(rn))^n$.

Thursday, June 29, 2023 3:00 pm - 3:00 pm EDT (GMT -04:00)

Graphs and Matroids Seminar - Jane Gao

Title: Minors of random representable matroid over finite fields

Speaker: Jane Gao
Affiliation: University of Waterloo
Location: MC 5479

Abstract: Consider a random n by m matrix A over GF(q) where every column has k nonzero elements, and let M[A] be the matroid represented by A. In the case that q=2, Cooper, Frieze and Pegden (RSA 2019) proved that given a fixed binary matroid N, if k is sufficiently large, and m/n is sufficiently large (both depending on N), then whp. M[A] contains N as a minor. We improve their result by determining the sharp threshold (of m/n) for the appearance of a fixed q-nary matroid N as a minor of M[A], for every k\ge 3, and every prime q. This is joint work with Peter Nelson.

Friday, June 30, 2023 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Andy Zucker

Title: Ramsey degrees, big and small

Speaker: Andy Zucker
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Many of the seminal results in finite Ramsey theory can be phrased by saying that a certain class of finite structures has the Ramsey property, such as the ordinary finite Ramsey theorem (the class of finite linear orders), the dual Ramsey theorem (the class of finite lex-ordered Boolean algebras), the Graham-Leeb-Rothschild theorem (the class of lex-ordered, finite-dimensional vector spaces over a fixed finite field), and the Nesetril-Rodl theorem (the class of finite ordered triangle-free graphs, among many others).

Tuesday, July 4, 2023 2:30 pm - 2:30 pm EDT (GMT -04:00)

URA Seminar - Bethany Caldwell

Title: Douglas–Rachford Algorithm for Control- and State-constrained Optimal Control Problems

Speaker: Bethany Caldwell
Affiliation: University of Waterloo
Location: MC 5501

Abstract: The Douglas - Rachford algorithm has been applied to many optimization problems due to its simplicity and efficiency but the application of this algorithm to optimal control is less common. In this talk we utilize this method to solve state- and control-constrained linear-quadratic optimal control problems.