research
∙
07/19/2023
Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses
We study Glauber dynamics for sampling from discrete distributions μ on ...
share
research
∙
05/10/2023
Optimal mixing of the down-up walk on independent sets of a given size
Let G be a graph on n vertices of maximum degree Δ. We show that, for an...
research
∙
11/01/2022
Composable Coresets for Constrained Determinant Maximization and Beyond
We study the task of determinant maximization under partition constraint...
research
∙
06/10/2022
On the Complexity of Sampling Redistricting Plans
A crucial task in the political redistricting problem is to sample redis...
research
∙
04/06/2022
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
We design fast algorithms for repeatedly sampling from strongly Rayleigh...
research
∙
03/21/2022
Improved Sampling-to-Counting Reductions in High-Dimensional Expanders and Faster Parallel Determinantal Sampling
We study parallel sampling algorithms for classes of distributions defin...
research
∙
03/08/2022
Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain
Let G = (V,E) be an undirected graph with maximum degree Δ and vertex co...
research
∙
11/05/2021
Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities
We introduce a framework for obtaining tight mixing times for Markov cha...
research
∙
09/14/2021
Domain Sparsification of Discrete Distributions using Entropic Independence
We present a framework for speeding up the time it takes to sample from ...
research
∙
06/08/2021
Entropic Independence in High-Dimensional Expanders: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Polynomials and the Ising Model
We introduce a notion called entropic independence for distributions μ d...
research
∙
05/03/2021
Spectral independence, coupling with the stationary distribution, and the spectral gap of the Glauber dynamics
We present a new lower bound on the spectral gap of the Glauber dynamics...
research
∙
02/16/2021
On the sampling Lovász Local Lemma for atomic constraint satisfaction problems
We study the problem of sampling an approximately uniformly random satis...
research
∙
02/10/2021
Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs
Determinantal point processes (DPPs) are widely popular probabilistic mo...
research
∙
02/04/2021
Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More
We show fully polynomial time randomized approximation schemes (FPRAS) f...
research
∙
11/24/2020
Towards the sampling Lovász Local Lemma
Let Φ = (V, 𝒞) be a constraint satisfaction problem on variables v_1,…, ...
research
∙
04/26/2020
An Extension of Plücker Relations with Applications to Subdeterminant Maximization
Given a matrix A and k≥ 0, we study the problem of finding the k× k subm...
research
∙
04/07/2019
