2020-21 Seminars

This talk introduces a directed analog of the classical Laplacian matrix and discusses algorithms for solving certain problems related to them. Of particular interest is that using such algorithms, one can compute the stationary distribution of a...

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours.  The study of rainbow subgraphs goes back to the work of Euler on Latin squares in the 18th century.  Since then rainbow structures were the focus of...

This talk gives an introduction on how to quickly solve linear systems where the matrix of the system is the Laplacian matrix of any undirected graph. No prior familiarity with optimization is assumed. In the process, we will cover:

• what positive...

We consider the Glauber dynamics (also called Gibbs sampling) for sampling from a discrete distribution in high-dimensional space (e.g., selecting a uniformly random legal coloring or independent set in a given graph, or selecting a "typical" state...

Expander graphs are graphs which simultaneously are both sparse and highly connected. The theory of expander graphs received a lot of attention in the past half a century, from both computer science and mathematics. In recent years, a new theory of...

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials P-n in n variables...