15 problems

Let $G\sim\mathcal{G}(n,n,d/n)$ be an Erdős–Rényi random bipartite graph, formed by independently including each edge between the two parts with probability $d/n$, and let…

Let $G$ be a random $\Delta$-regular bipartite graph, and let $Z_{G,q}(\beta)$ be the partition function of the anti-ferromagnetic $q$-state Potts model on $G$. Random-regular-grap…

Let $Z_{G,q}(\beta)$ denote the partition function of the anti-ferromagnetic $q$-state Potts model on a graph $G$, and let the tree-uniqueness threshold be the range of inverse tem…

Let BIS denote the problem of approximating the number of independent sets of a bipartite graph, and let an FPRAS be a fully polynomial randomized approximation scheme. Goldberg–Je…

Potts sampling conjecture below $\beta_c$. When $\beta<\beta_c$, sampling from the ferromagnetic Potts model admits a polynomial-time algorithm.

Deterministic approximate counting conjecture. Such algorithms should exist provided

Let $\Delta$ be a maximum-degree bound, let $q\ge 2\Delta$, and consider graphs of maximum degree at most $\Delta$. A $q$-list packing assigns colors from each vertex's list so tha…

Let $\#\mathrm{BIS}$ denote the problem of counting independent sets in a bipartite graph, let an FPRAS be a fully polynomial-time randomized approximation scheme, and let…

Quantum approximate counting intermediate-class conjecture. Quantum approximate counting is not $\#\mathsf{P}$-hard; equivalently, it defines an intermediate class lying somewhere…

Let $P$ be a $0/1$ polytope, and let $G(P)$ be its graph, whose vertices are the vertices of $P$ and whose edges join pairs of vertices spanning an edge of $P$. Consider the simple…

Algorithmic transition conjecture. For the colourings model and the antiferromagnetic Potts model, the uniqueness phase transition on the $d$-ary tree captures the computational co…

Let an FPRAS be a fully polynomial randomized approximation scheme, and let $\#\mathrm{BIS}$ denote the problem of approximately counting independent sets in a bipartite graph. An…

Counting-colorings conjecture. There is a fully polynomial-time approximation scheme, deterministic or randomized (FPTAS/FPRAS), for counting the number of proper $q$-colorings of…

FPTAS–Gibbs uniqueness conjecture. An FPTAS for counting proper colorings exists for every arbitrary graph whenever

Mossel–Weitz–Wormald conjecture. Unless $\mathrm{NP}=\mathrm{RP}$, there does not exist a fully polynomial approximation scheme for the partition function of the hardcore model wit…