Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Matthew Jenssen: Algorithms for #BIS-hard problems on expander graphs

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

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When Oct 09, 2018
from 04:00 PM to 05:00 PM
Add event to calendar vCal
iCal

Title: Algorithms for #BIS-hard problems on expander graphs

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) $\Delta$-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 $\Delta$-regular tree. Joint work with Peter Keevash and Will Perkins.

Document Actions