25 citations · 70 across the 30 of their papers we have counts for
8 papers · 1 filter
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^*(…
Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial
Asaf Ferber, Vishesh Jain, Ashwin Sah +1
Conditional on the extended Riemann hypothesis, we show that with high probability, the characteristic polynomial of a random symmetric -matrix is irreducible. This addr…
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…
Rank deficiency of random matrices
Vishesh Jain, Ashwin Sah, Mehtaab Sawhney
Let be a random matrix with i.i.d. entries. We show that for fixed , \[\lim_{n\to \infty}\frac{1}{n}\log_2\mathbb{P}[\text{corank…
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…
Anticoncentration versus the number of subset sums
Vishesh Jain, Ashwin Sah, Mehtaab Sawhney
Let . We show that for any , if \[\#\{\vecξ \in \{0,1\}^{n}: \langle \vecξ, \vec{w} \rangle = τ\} \ge 2^{-εn}\cdot 2…