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, 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.

Monday, July 18, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory Seminar - Sabrina Lato

Title: New Characterizations of Distance-Biregular Graphs

Speaker: Sabrina Lato
Affiliation: University of Waterloo
Location: please contact Sabrina Lato for Zoom link

Abstract: Fiol, Garriga, and Yebra introduced the notion of pseudo-distance-regular vertices, and were able to use this notion to come up with a characterization of when a graph is distance-regular. Subsequently, Fiol and Garriga were able to use pseudo-distance-regular vertices and a bound on the excess of a vertex to come up with another characterization of distance-regular graphs. We will present an overview of their results, as well as recent extensions to distance-biregular graphs.

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

Graph and Matroids Seminar - Matt Kroeker

Title: High-Rank Matroids and Unavoidable Flats

Speaker: Matt Kroeker
Affiliation: University of Waterloo
Location: MC 5417

Abstract: We discuss a variety of questions and results pertaining to conjectures of Geelen from 2021 on the unavoidable flats in matroids of sufficiently high rank. We will also explore the differences in how such questions are posed for various classes of matroids, why such differences are necessary, and how they could potentially be reconciled. A result for the class of binary matroids and an outline of its proof will be discussed in detail. Joint work with Jim Geelen.

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

Tutte Colloquium - Krystal Guo

Title: Strongly regular graphs with a regular point 

Speaker: Krystal Guo
Affiliation: University of Amsterdam, Korteweg-de Vries Institute 
Location MC 5501 or please contact Melissa Cambridge for the Zoom link

Abstract:  Arising from Hoffman and Singleton's study of Moore graphs, strongly regular graphs play an important role in algebraic graph theory. Strongly regular graphs can be construct from geometric objects, such as generalized quadrangles and certain geometric properties, such as having a regular point, can be studied in the context of graphs.

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

Algebraic Combinatorics Seminar - Jinyoung Park

Title: Thresholds

Speaker: Jinyoung Park
Affiliation: Standford University
Location: Please contact Logan Crew for the Zoom link

Abstract: Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will present recent progress on this topic. Based on joint work with Huy Tuan Pham.

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

Tutte Colloquium - Amy Wiebe

Title: Non-realizability of polytopes via linear programming

Speaker: Amy Wiebe
Affiliation: UBC Okanagan
Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract: A classical question in polytope theory is whether an abstract polytope can be realized as a concrete convex object. Beyond dimension 3, there seems to be no concise answer to this question in general. In specific instances, answering the question in the negative is often done via “final polynomials” introduced by Bokowski and Sturmfels. This method involves finding a polynomial which, based on the structure of a polytope if realizable, must be simultaneously zero and positive, a clear contradiction.

Friday, October 7, 2022 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Richard Peng

Title: Bipartite Matching in Almost-Linear Time and More

Speaker: Yang Peng
Affiliation: University of Waterloo
Location: MC 5501, please contact Amanda Lutz for Zoom link

Abstract:  This talk will present an algorithm that computes maximum bipartite matchings in m^{1 + o(1)} time, and discuss its connections with optimization, graph algorithms, and data structures.

Friday, November 25, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Stefan Weltge

Title: Integer programs with bounded subdeterminants and two nonzeros per row

Speaker: Stefan Weltge
Affiliation: Technical University of Munich
Location: MC 5501 or contact Eva Lee for Zoom link

Abstract: Determining the complexity of integer linear programs with integer coefficient matrices whose subdeterminants are bounded by a constant is currently a very actively discussed question in the field. In this talk, I will present a strongly polynomial-time algorithm for such integer programs with the further requirement that every constraint contains at most two variables. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k = 0 (bipartite graphs) and for k = 1.

This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky, which recently appeared at FOCS this year.

Friday, December 9, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Vijay Bhattiprolu

Titile: Global geometric reductions for some bottleneck questions in hardness of approximation

Speaker: Vijay Bhattiprolu
Affiliation: University of Waterloo
Location: MC 5501 or contact Eva Lee for Zoom link

Abstract: I will describe the classical "local gadget reduction" paradigm for proving hardness of approximation results and then list some important optimization problems that resist all such attacks. With a focus on problems that can be cast as quadratic maximization over convex sets, I will describe some successes in bypassing the aforementioned bottleneck using ideas from geometry. Time permitting I will also describe some compelling new frontiers where answering some questions in convex geometry could be the path forward.

Friday, December 16, 2022 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte Colloquium - Daniel Panario

Title: Probabilistic root finding in code-based cryptography

Speaker: Daniel Panario
Affiliation: School of Mathematics and Statistics, Carleton University
Location: MC 5501 or contact Eva Lee for Zoom link

Abstract: Factorization of polynomials over finite fields, and the particular subproblem of finding roots of polynomials, have many applications in diverse areas such as computer algebra, cryptography and coding theory, among many others. In practice, fast factorization algorithms are probabilistic.