Clayton Mizgerd

activity

20212026

collaborators

10 papers

cs.DS2026

Transposition achieves OPT $+ O (1)$ 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 $i$ -th element costs $i$ . Items will be queried in an IID manner a…

cs.DS2026

A general counting and sampling Lovász local lemma

Vishesh Jain, Clayton Mizgerd, Huy Tuan Pham

Consider a constraint satisfaction problem $C$ on finitely many independent random variables with dependency graph $G$ . Let $p_{a}$ be the violation probability of a constra…

math.PR2026

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 $S^{n - 1}$ started from a coordinate vector. The cutoff occurs at $C_{BRW} n lo g n$ , where $C_…

cs.DS2026

The online monotone array completion problem

Vishesh Jain, Dylan King, Clayton Mizgerd

Consider the following online filling game. An array of length $n$ is initially empty. At each time step one observes an independent sample from $Unif [0, 1]$ and must eithe…

math.ST2026

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…

math.CO2026

Equality in Fill's spectral gap problem

Vishesh Jain, Clayton Mizgerd

We study the adjacent-transposition chain on the symmetric group $S_{n}$ with a regular parameter vector $p = (p_{i, j})_{i \neq = j}$ . Fill's spectral gap conjecture, r…

cs.DS2026

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 $k$ -c…

math.CO2025

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 $Θ (n^{3/2} (lo g n)^{1/2})$ edges and establish the width of the scaling window for the transitions…

math.CO2025

The random graph process is globally synchronizing

Vishesh Jain, Clayton Mizgerd, Mehtaab Sawhney

The homogeneous Kuramoto model on a graph $G = (V, E)$ is a network of $∣ V ∣$ identical oscillators, one at each vertex, where every oscillator is coupled bidirectionally (with unit…

cond-mat.stat-mech2021

Critical points of the random cluster model with Newman-Ziff sampling

Tolson H. Bell, Jerrell M. Cockerham, Clayton M. Mizgerd +2

We present a method for computing transition points of the random cluster model using a generalization of the Newman-Ziff algorithm, a celebrated technique in numerical percolation…

Transposition achieves OPT+O(1) in polynomial time for IID list update

A general counting and sampling Lovász local lemma

Total variation cutoff for Kac's walk on the sphere

The online monotone array completion problem

Thinned Quantile Shares are Universally Feasible

Equality in Fill's spectral gap problem

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity

On the chromatic number of random triangle-free graphs

The random graph process is globally synchronizing

Critical points of the random cluster model with Newman-Ziff sampling

Transposition achieves OPT $+ O (1)$ in polynomial time for IID list update