Trickle-down is a phenomenon in high-dimensional expanders with many important
applications—for example, it is a key ingredient in various constructions of high-dimensional …

We show conditional lower bounds for well-studied# P-hard problems: The number of
satisfying assignments of a 2-CNF formula with n variables cannot be computed in time exp …

We consider Ising models on the hypercube with a general interaction matrix $ J $, and give
a polynomial time sampling algorithm when all but $ O (1) $ eigenvalues of $ J $ lie in an …

Abstract Multimarginal Optimal Transport (MOT) has attracted significant interest due to
applications in machine learning, statistics, and the sciences. However, in most applications …

We provide evidence that it is computationally difficult to approximate the partition function of
the ferromagnetic q-state Potts model when q> 2. Specifically, we show that the partition …

Submodular optimization has found many applications in machine learning and beyond. We
carry out the first systematic investigation of inference in probabilistic models defined …

Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix
elements in the standard product basis are real and non-positive. Many interesting quantum …

Instantaneous quantum polynomial-time (IQP) computation is a class of quantum
computation consisting only of commuting two-qubit gates and is not universal …

By implementing algorithmic versions of Sapozhenko's graph container methods, we give
new algorithms for approximating the number of independent sets in bipartite graphs. Our …

In this paper we describe how MAP inference can be used to sample efficiently from Gibbs
distributions. Specifically, we provide means for drawing either approximate or unbiased …