Events

Title: A proof of the Hell-Nešetřil Dichotomy via Siggers Polymorphisms

Abstract:

In 2017, the constraint satisfaction dichotomy was proven via techniques from universal algebra. If we restrict this theorem to graphs, we get the Hell-Nešetřil Dichotomy, which is a statement about colouring graphs.

Title: High dimensional probability: Estimation in high dimensions

Abstract:

In this talk, we discuss high dimensional estimation problems. The aim is to estimate some point x in a given ambient bounded space K using a small number of independent random observations.

Title: Online Competitive Algorithms for Resource Allocation

Abstract:

In online optimization with budgets, the data in the optimization problem is revealed over time. At each step a decision variable needs to be set without knowing the future inputs, while there is a budget constraint that couples the decisions across time.

Title: Erdös-Rényi Graphs

Abstract:

These might not be the Erdös-Rényi graphs you first thought of. Let V be a 3-dimensional vector space over a field of odd order q.

Title: Optimal detection of sparse principal components in high dimension

Abstract:

I will present the paper with this title by Berthet and Rigollet (Ann. Stat., 41 (2013) 1780-1815, https://projecteuclid.org/download/pdfview_1/euclid.aos/1378386239). 

Title: Graph Sparsification by Effective Resistances

Abstract:

We will discuss an application of the matrix concentration inequalities of Tropp to spectral sparsification of graphs.

Title: Recovery of a mixture of Gaussians by sum-of-norms clustering

Abstract:

Sum-of-norms clustering is a method for assigning n points in R^d to K clusters, 1 ≤ K ≤ n, using convex optimization.

Title: From Warragul to Waterloo

Abstract:

As Tom Lehrer once said “Some of you may have run into mathematicians, and therefore had occasion to wonder how they got that way”; this talk will be a partial explanation of how I got this way.

Title: The Erdős-Pósa property for A-paths

Abstract:

Let A be a set of vertices in a graph G. An A-path is a path whose ends are in A. Gallai proved, for any integer k, that there are either k disjoint A-paths or there is a set of at most 2k vertices that hit all A-paths.

Title: The 600-cell

Abstract:

If d ≥ 5, then in R^d there are exactly three regular polytopes (simple, hypercube, dual hypercube). If d = 3 we have the icosahedron and the dodecahedron in addition. If d = 4, there are again two exceptional regular polytopes, the so-called 120-cell and 600-cell.