From the 1 of 7 linked papers with an AI index.
7 papers
Total variation cutoff for Kac's walk on the sphere
Vishesh Jain, Clayton Mizgerd
The paper proves that the discrete-time Kac walk on the (n‑1)-dimensional sphere, started from a coordinate vector, exhibits a total‑variation cutoff at time C_{BRW}·n·log n (with…
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…
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…
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…
On the chromatic number of random triangle-free graphs
Clayton Mizgerd, Will Perkins, Yuzhou Wang
We study the chromatic number of typical triangle-free graphs with edges and establish the width of the scaling window for the transitions…