1 citations · 1 across the 18 of their papers we have counts for
5 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…
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…
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…
Rapid mixing of the down-up walk on matchings of a fixed size
Vishesh Jain, Clayton Mizgerd
Let be a graph on vertices and let denote the size of a maximum matching in . We show that for any and for any , the d…