4 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…
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…