Simons Collaboration on Algorithms and Geometry Monthly Meeting, November 2020

John Peebles
Directed Laplacian Matrices and Algorithms for Them

This talk introduces a directed analog of the classical Laplacian matrix and discusses algorithms for solving certain problems related to them, as well as open questions. Of particular interest is that using such algorithms, one can compute the stationary distribution of a Markov chain to high accuracy with a number of arithmetic operations close to the number of possible transitions. The analogous problem in the low space setting, in contrast, remains open.
 

Or Zamir
Breaking the 2^n barrier for 5-coloring and 6-coloring

The problem of k-coloring a graph, or determining the chromatic number of a graph (i.e., finding the smallest k for which the graph is k-colorable) is another one of the most classic and well studied NP-Complete problems. Following a long line of work, Bjorklund, Husfeldt and Koivisto showed in 2009 that the chromatic number of a graph can be computed in O*(2^n) time, where n is the number of vertices in the graph. Deciding whether a graph is 3-colorable can be done in O(1.33^n) time (Beigel and Eppstein, 2005) and deciding whether it is 4-colorable can be done in O(1.73^n) time (Fomin, Gaspers and Saurabh, 2007). Surprisingly, for k>4 no improvements over the general O^*(2^n) were known.

In the discussed work, we show that both 5-coloring and 6-coloring can also be solved in O((2-eps)^n) time for some eps>0. As a crucial step, we obtain an exponential improvement for computing the chromatic number of a very large family of graphs. In particular, for any constants D,a>0, the chromatic number of graphs with at least a*n vertices of degree at most D can be computed in O((2-eps)^n) time, for some eps = eps_{D,a} > 0. This statement generalizes previous results for bounded-degree graphs (Bjorklund, Husfeldt, Kaski, and Koivisto, 2010) and graphs with bounded average degree (Golovnev, Kulikov and Mihajilin, 2016).