Computer Science and Discrete Mathematics (CSDM)

What edge density of a graph guarantees that that it will contain a particular subgraph? Or one of a given family F of subgraphs? The celebrated Erdős--Stone--Simonovits Theorem characterizes the maximum edge density in F-free graphs, in terms of...

Bernstein's theorem (also known as the Bernstein-Khovanskii-Kushnirenko theorem) gives a bound on the number of nonzero solutions of a polynomial system of equations in terms of the mixed volume of its Newton polytopes. In this talk, we will give...

Random sampling a subgraph of a graph is an important algorithmic technique.  Solving some problems on the (smaller) subgraph is naturally faster, and can give either a useful approximate answer, or sometimes even give a result that can be quickly...

For a fixed integer k > 1, the Boolean k-XOR problem consists of a system of linear equations mod 2 with each equation involving exactly k variables. We give an algorithm to strongly refute *semi-random* instances of the Boolean k-XOR problem on n...

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