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
∙
12/12/2022
Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings
We show that the threshold for the binomial random 3-partite, 3-uniform ...
research
∙
06/09/2022
Spencer's theorem in nearly input-sparsity time
A celebrated theorem of Spencer states that for every set system S_1,…, ...
research
∙
05/03/2022
Optimal minimization of the covariance loss
Let X be a random vector valued in ℝ^m such that X_2≤ 1 almost surely. F...
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
∙
08/02/2021
Approximate counting and sampling via local central limit theorems
We give an FPTAS for computing the number of matchings of size k in a gr...
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
∙
01/19/2021
Anticoncentration versus the number of subset sums
Let w⃗ = (w_1,…, w_n) ∈ℝ^n. We show that for any n^-2≤ϵ≤ 1, if #{ξ⃗...
research
∙
11/24/2020
Towards the sampling Lovász Local Lemma
Let Φ = (V, 𝒞) be a constraint satisfaction problem on variables v_1,…, ...
research
∙
09/03/2020
On the smoothed analysis of the smallest singular value with discrete noise
Let A be an n× n real matrix, and let M be an n× n random matrix whose e...
research
∙
07/13/2020
Perfectly Sampling k≥ (8/3 +o(1))Δ-Colorings in Graphs
We present a randomized algorithm which takes as input an undirected gra...
research
∙
05/18/2020
On the real Davies' conjecture
We show that every matrix A ∈R^n× n is at least δ A-close to a real ...
research
∙
03/23/2020
Kac meets Johnson and Lindenstrauss: a memory-optimal, fast Johnson-Lindenstrauss transform
Based on the Kac random walk on the orthogonal group, we present a fast ...
research
∙
08/29/2019
Smoothed analysis of the least singular value without inverse Littlewood-Offord theory
We study the lower tail behavior of the least singular value of an n× n ...
research
∙
05/24/2019
Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation
The analysis of Belief Propagation and other algorithms for the reconst...
research
∙
09/13/2018
Towards the linear arboricity conjecture
The linear arboricity of a graph G, denoted by la(G), is the minimum num...
research
∙
08/22/2018
Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
The free energy is a key quantity of interest in Ising models, but unfor...
research
∙
03/28/2018
1-factorizations of pseudorandom graphs
A 1-factorization of a graph G is a collection of edge-disjoint perfect ...
research
∙
02/16/2018
The Vertex Sample Complexity of Free Energy is Polynomial
We study the following question: given a massive Markov random field on ...
research
∙
02/16/2018
The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
The mean field approximation to the Ising model is a canonical variation...
research
∙
11/05/2017