research
∙
09/11/2023
Influence Maximization in Ising Models
Given a complex high-dimensional distribution over {± 1}^n, what is the ...
share
research
∙
07/17/2023
Combinatorial Approach for Factorization of Variance and Entropy in Spin Systems
We present a simple combinatorial framework for establishing approximate...
research
∙
04/27/2023
Fast Sampling of b-Matchings and b-Edge Covers
For an integer b ≥ 1, a b-matching (resp. b-edge cover) of a graph G=(V,...
research
∙
04/04/2023
Strong spatial mixing for colorings on trees and its algorithmic applications
Strong spatial mixing (SSM) is an important quantitative notion of corre...
research
∙
07/19/2022
Identity Testing for High-Dimensional Distributions via Entropy Tensorization
We present improved algorithms and matching statistical and computationa...
research
∙
07/06/2022
From algorithms to connectivity and back: finding a giant component in random k-SAT
We take an algorithmic approach to studying the solution space geometry ...
research
∙
04/05/2022
Almost-Linear Planted Cliques Elude the Metropolis Process
A seminal work of Jerrum (1992) showed that large cliques elude the Metr...
research
∙
06/07/2021
Spectral Independence via Stability and Applications to Holant-Type Problems
This paper formalizes connections between stability of polynomials and c...
research
∙
05/04/2021
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region
For spin systems, such as the q-colorings and independent-set models, ap...
research
∙
03/12/2021
On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization
For general spin systems, we prove that a contractive coupling for any l...
research
∙
11/04/2020
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
We prove an optimal mixing time bound on the single-site update Markov c...
research
∙
07/16/2020
The Swendsen-Wang Dynamics on Trees
The Swendsen-Wang algorithm is a sophisticated, widely-used Markov chain...
research
∙
07/16/2020
Rapid Mixing for Colorings via Spectral Independence
The spectral independence approach of Anari et al. (2020) utilized recen...
research
∙
04/22/2020
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
We study identity testing for restricted Boltzmann machines (RBMs), and ...
research
∙
04/20/2020
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
For general antiferromagnetic 2-spin systems, including the hardcore mod...
research
∙
05/07/2019
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logc...
research
∙
01/22/2019
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
We study the identity testing problem in the context of spin systems or ...
research
∙
01/20/2019
Markov chains for the hard-core model via polymer models
Jenssen, Keevash and Perkins give an FPTAS and an efficient sampling alg...
research
∙
06/12/2018
Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region
The Swendsen-Wang dynamics is a popular algorithm for sampling from the ...
research
∙
08/17/2017