Events

Title: Using Lasserre Hierarchy for Graph Coloring  

Abstract:

In this talk, I will go over a technique introduced by Arora and Ge for coloring 3-colorable graphs having low threshold rank (i.e., graphs with few eigenvalues below certain negative constant).

Title: Toward a Theory of Crossing-Critical Graphs

Abstract: 

The crossing number of a graph is defined as the minimum number of crossings of edges in a drawing of the graph in the plane. In his seminal 1970 paper Toward a Theory of Crossing Numbers, Tutte made a fundamental contribution by proving what is known today as the Hanani-Tutte Theorem.

Title: IETF encryption standards post-TLS 1.3

Abstract:

TLS is one of the most important security protocols online. It’s most famously used in web browsing, providing the S in HTTPS.

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: The Perron-Frobenius Theorem

Abstract:

The Perron-Frobenius Theorem is an extremely important result on eigenvalues and eigenvectors of non-negative matrices.

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.