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:
Friday, November 26, 2021 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Ashwin Nayak

Title: Quantum Distributed Complexity of Graph Diameter and Set Disjointness

Speaker: Ashwin Nayak
Affiliation:

University of Waterloo

Zoom: Please email Emma Watson

Abstract:

In the Congest model, a network of p processors cooperate to solve some distributed task. Initially, each processor knows only its unique label, the labels of its neighbours, and a polynomial upper bound on p, the size of the network. The processors communicate with their neighbours in rounds. In each round, a processor may perform local (quantum) computation, and send a short message to each of its neighbours. How many rounds of communication are required for some processor to compute the diameter of the network?

Monday, February 7, 2022 11:30 am - 11:30 am EST (GMT -05:00)

Algebraic Graph Theory Seminar - Gabriel Coutinho

Title: Optimizing sums of eigenvalues

Speaker: Gabriel Coutinho
Affiliation: Universidade Federal de Minas Gerais
Zoom: Contact Sabrina Lato

Abstract:

In its original proof, Hoffman's well known lower bound to the chromatic number is obtained after replacing several terms of a sum of eigenvalues by the smallest eigenvalue of the graph.

Friday, March 4, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Mireille Bousquet-Mélou

Title: Counting planar maps, 50 years after William Tutte

Speaker: Mireille Bousquet-Mélou
Affiliation: CNRS, Université de Bordeaux
Location: MC 5501 or please contact Emma Watson for Zoom link

Abstract:

Every planar map can be properly coloured with four colours. But how many proper colourings has, on average, a planar map with $n$ edges? What if we allow a prescribed number of "monochromatic" edges, the endpoints of which share the same colour? What if we have $q$ colours rather than four?

Tuesday, March 8, 2022 4:00 pm - 4:00 pm EST (GMT -05:00)

Graphs and Matroids Seminar - Sang-il Oum

Title: Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k

Speaker: Sang-il Oum
Affiliation: Institute for Basic Science / KAIST
Zoom: Join via http://matroidunion.org/?page_id=2477 or please email Shayla Redlin

Abstract:

Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field $\mathbb F$, the list contains only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)].

Thursday, June 23, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Cryptography Reading Group - Raghvendra Rohit

Title: On the Security of the NIST lightweight Finalist Ascon

Speaker: Raghvendra Rohit
Affiliation: Technology Institute in Abu Dhabi
Zoom: Please contact Jesse Elliott for zoom link

Abstract: 

The ongoing NIST lightweight cryptographic standardization project for the selection of ciphers which are suitable for constrained environments is in the final stage. The authenticated encryption algorithm Ascon, designed by Dobrauing et al., is one out of the 10 finalists. Ascon is also one of the winners of the CAESAR competition in the lightweight applications category.

Tuesday, July 5, 2022 2:30 pm - 2:30 pm EDT (GMT -04:00)

Graph and Matroids Seminar - Sepehr Hajebi

Title: Bounded treewidth in hereditary graph classes

Speaker: Sepehr Hajebi
Affiliation: University of Waterloo
Location: MC 5417

Abstract: A highlight of the superb graph minors project of Robertson and Seymour is their so-called Grid Theorem: a minor-closed class of graphs has bounded treewidth if and only it does not contain all planar graphs. Which induced-subgraph-closed graph classes have bounded treewidth?

Thursday, July 7, 2022 1:00 pm - 1:00 pm EDT (GMT -04:00)

Algebraic Combinatorics Seminar - Emily Gunawan

Title: Box-ball systems, RSK, and Motzkin paths 

Speaker: Emily Gunawan
Affiliation: University of Oklahoma
Location: MC 5479, please contact Olya Mandelshtam for Zoom link.

Abstract:  A box-ball system (BBS) is a discrete dynamical system whose dynamics come from the balls jumping according to certain rules. A permutation on n objects gives a BBS state by assigning its one-line notation to n consecutive boxes. After a finite number of steps, a box-ball system will reach a steady state. From any steady state, we can construct a tableau called the soliton decomposition of the box-ball system.

Thursday, July 14, 2022 1:00 pm - 1:00 pm EDT (GMT -04:00)

Algebraic Combinatorics Seminar - Kevin Purbhoo

Title: An identity in the group algebra of the symmetric group

Speaker: Kevin Purbhoo
Affiliation: University of Waterloo
Location: MC 5479, contact Olya Mandelshtam for Zoom link

Abstract: Come with me on a magical journey into the mysterious world of inverse Wronskians.

Friday, July 15, 2022 1:00 pm - 1:00 pm EDT (GMT -04:00)

Combinatorial Optimization Reading Group - Ricardo Fukasawa

Title: Stochastic Optimization

Speaker: Ricardo Fukaswaw
Affiliation: University of Waterloo
Location MC 6029 or please contact Rian Neogi for Zoom link

Abstract:  While deterministic optimization problems are very useful in practice, often times the assumption that all data is known in advance does not hold true. One possible way to relax this assumption is to assume that the data depends on random variables.

Friday, July 15, 2022 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - William Slofstra

Title: Positivity and sums of squares in products of free algebras

Speaker: William Slofstra
Affiliation: University of Waterloo
Location MC 5501 or please contact Melissa Cambridge for Zoom link

Abstract: A noncommutative polynomial is said to be positive relative to some constraints if plugging matrices (or more generally, operators on a Hilbert space) satisfying the constraints into the polynomial always yields a positive operator. It is a natural problem to determine whether or not a given polynomial is positive, and if it is, to find some certificate of positivity. This problem is closely connected with noncommutative polynomial optimization, where we want to find matrices or operators that maximize the operator norm of some polynomial, subject to the constraint that some other polynomials in the operators are positive or vanish. When the algebra cut out by the constraints is a free algebra, free group algebra, or similar algebra, it's well-known that a polynomial is positive on operators satisfying the constraints if and only if it's a sum of Hermitian squares in the algebra.