7 papers · 1 filter
Transposition achieves OPT in polynomial time for IID list update
Clayton Mizgerd
In the classical list update problem, a set of items must be stored in a list-type structure, where accessing the -th element costs . Items will be queried in an IID manner a…
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…
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…
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…
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…