Matthew Jenssen : Algorithms for #BIS-hard problems on expander graphs

Posted by Will Perkins , part of the Mathematical Computer Science Seminar.

At

Dec. 3, 2018, 4 p.m.

In

427 SEO

Abstract

We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) d-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite d-regular tree. Joint work with Peter Keevash and Will Perkins.

Note the non-standard time