25 citations · 70 across the 30 of their papers we have counts for
10 papers · 1 filter
Optimal mixing of the down-up walk on independent sets of a given size
Vishesh Jain, Marcus Michelen, Huy Tuan Pham +1
Let be a graph on vertices of maximum degree . We show that, for any , the down-up walk on independent sets of size mixes in time $O_{Δ,δ}(k\…
Spencer's theorem in nearly input-sparsity time
Vishesh Jain, Ashwin Sah, Mehtaab Sawhney
A celebrated theorem of Spencer states that for every set system , there is a coloring of the ground set with with discrepancy $O(\sqrt{n\…
Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities
Nima Anari, Vishesh Jain, Frederic Koehler +2
We introduce a framework for obtaining tight mixing times for Markov chains based on what we call restricted modified log-Sobolev inequalities. Modified log-Sobolev inequalities (M…
Approximate counting and sampling via local central limit theorems
Vishesh Jain, Will Perkins, Ashwin Sah +1
We give an FPTAS for computing the number of matchings of size in a graph of maximum degree on vertices, for all , where is fixed and $m^*(…
Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models
Nima Anari, Vishesh Jain, Frederic Koehler +2
We introduce a notion called entropic independence that is an entropic analog of spectral notions of high-dimensional expansion. Informally, entropic independence of a background d…
Spectral independence, coupling with the stationary distribution, and the spectral gap of the Glauber dynamics
Vishesh Jain, Huy Tuan Pham, Thuy Duong Vuong
We present a new lower bound on the spectral gap of the Glauber dynamics for the Gibbs distribution of a spectrally independent -spin system on a graph with maximum…
On the sampling Lovász Local Lemma for atomic constraint satisfaction problems
Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong
We study the problem of sampling an approximately uniformly random satisfying assignment for atomic constraint satisfaction problems i.e. where each constraint is violated by only…
Towards the sampling Lovász Local Lemma
Vishesh Jain, Huy Tuan Pham, Thuy Duong Vuong
Let be a constraint satisfaction problem on variables such that each constraint depends on at most variables and such that each variable…
Perfectly Sampling -Colorings in Graphs
Vishesh Jain, Ashwin Sah, Mehtaab Sawhney
We present a randomized algorithm which takes as input an undirected graph on vertices with maximum degree , and a number of colors , and returns…
Fast and memory-optimal dimension reduction using Kac's walk
Vishesh Jain, Natesh S. Pillai, Ashwin Sah +2
In this work, we analyze dimension reduction algorithms based on the Kac walk and discrete variants. (1) For points in , we design an optimal Johnson-Lindenstra…