Simons Collaboration on Algorithms and Geometry Monthly Meeting, November 2020

Date & Time

10:00 AM – 12:15 PM

  • Agendaplus--large

    Friday, November 20th (online)

    10:00 - 11:00 AM John Peebles - Directed Laplacian Matrices and Algorithms for Them
    11:00 - 11:15 AM Break
    11:15 AM - 12:15 PM Breaking the 2^n barrier for 5-coloring and 6-coloring
  • Abstractsplus--large

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

Subscribe to MPS announcements and other foundation updates