1 citations · 1 across the 18 of their papers we have counts for
13 papers · 1 filter
A general counting and sampling Lovász local lemma
Vishesh Jain, Clayton Mizgerd, Huy Tuan Pham
Consider a constraint satisfaction problem on finitely many independent random variables with dependency graph . Let be the violation probability of a constra…
A deterministic approximation for the permanent of a nonnegative matrix
Dingding Dong, Vishesh Jain
For every fixed , we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix , returns satisfy…
Optimal girth-dependent bounds for the Bethe approximation of the permanent
Dingding Dong, Vishesh Jain
For an nonnegative matrix , the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe…
The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma
Vishesh Jain
The Johnson--Lindenstrauss lemma asserts that every set of points in -dimensional Euclidean space embeds into -dimensional Euclidean space with di…
On graphically local versions of metric embeddings
Vishesh Jain, Duan Tu
We consider the problem of graphically local metric embedding, i.e. embedding points from an arbitrary finite metric space into a target metric space while preserving, up to a smal…
Total variation cutoff for Kac's walk on the sphere
Vishesh Jain, Clayton Mizgerd
We prove cutoff in total variation distance for the discrete-time Kac walk on started from a coordinate vector. The cutoff occurs at , where $C_…
The online monotone array completion problem
Vishesh Jain, Dylan King, Clayton Mizgerd
Consider the following online filling game. An array of length is initially empty. At each time step one observes an independent sample from and must eithe…
On the maximum density of -graphs in which every -set spans or edges
Vishesh Jain, Haoran Luo, Dhruv Mubayi
In 1984, Frankl and Füredi asked for the maximum density of an -vertex -graph in which every -set of vertices spans or edges. They gave a construction with asy…
The size of the spanning-tree spectrum of simple graphs
Vishesh Jain
For a graph , let denote the number of spanning trees. We show that for every fixed , the number of distinct values of , as ranges over simple grap…
Thinned Quantile Shares are Universally Feasible
Vishesh Jain, Clayton Mizgerd, Shyam Ravichandran
Quantile shares, introduced by Babichenko, Feldman, Holzman, and Narayan [STOC 2024], offer an ordinal, self-maximizing, and interpretable benchmark for fair division of indivisibl…
Entropic independence via sparse localization
Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong
Entropic independence is a structural property of measures that underlies modern proofs of functional inequalities, notably (modified) log-Sobolev inequalities, via ``annealing'' o…
Equality in Fill's spectral gap problem
Vishesh Jain, Clayton Mizgerd
We study the adjacent-transposition chain on the symmetric group with a regular parameter vector . Fill's spectral gap conjecture, r…
Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
Vishesh Jain, Clayton Mizgerd, Eric Vigoda
Sampling graph colorings via local Markov chains is a central problem in approximate counting and Markov chain Monte Carlo (MCMC). We address the problem of sampling a random -c…