Vishesh Jain

activity

20222026

most citedDimension reduction for maximum matchings and the Fastest Mixing Markov Chain

1 citations · 1 across the 18 of their papers we have counts for

collaborators

18 papers

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…

cs.DS2026

A deterministic $(1 + ε)^{n}$ approximation for the permanent of a nonnegative matrix

Dingding Dong, Vishesh Jain

For every fixed $0 < ε \leq 1$ , we give a deterministic strongly polynomial algorithm that, given a nonnegative matrix $A \in R_{\geq 0}^{n \times n}$ , returns $Q$ satisfy…

math.CO2026

Optimal girth-dependent bounds for the Bethe approximation of the permanent

Dingding Dong, Vishesh Jain

For an $n \times n$ nonnegative matrix $A$ , the Bethe permanent, which is computable in deterministic polynomial time, satisfies the tight universal comparison \[\operatorname{Bethe…

cs.CG2026

The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

Vishesh Jain

The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$ -dimensional Euclidean space embeds into $O (ε^{- 2} lo g n)$ -dimensional Euclidean space with di…

cs.CG2026

On graphically local versions of metric embeddings

Vishesh Jain, Duan Tu

We consider the problem of graphically local metric embedding, i.e. embedding points from an arbitrary finite metric space into a target metric space while preserving, up to a smal…

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.CO2026

On the maximum density of $r$ -graphs in which every $(r + 1)$ -set spans $0$ or $2$ edges

Vishesh Jain, Haoran Luo, Dhruv Mubayi

In 1984, Frankl and Füredi asked for the maximum density of an $n$ -vertex $r$ -graph in which every $(r + 1)$ -set of vertices spans $0$ or $2$ edges. They gave a construction with asy…

math.CO2026

The size of the spanning-tree spectrum of simple graphs

Vishesh Jain

For a graph $G$ , let $τ (G)$ denote the number of spanning trees. We show that for every fixed $0 < c < 1/4$ , the number of distinct values of $τ (G)$ , as $G$ ranges over simple grap…

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…

cs.IT2026

Entropic independence via sparse localization

Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong

Entropic independence is a structural property of measures that underlies modern proofs of functional inequalities, notably (modified) log-Sobolev inequalities, via ``annealing'' o…

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

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…

math.PR2024

Hitting time mixing for the random transposition walk

Vishesh Jain, Mehtaab Sawhney

Consider shuffling a deck of $n$ cards, labeled $1$ through $n$ , as follows: at each time step, pick one card uniformly with your right hand and another card, independently and uni…

cs.DS2024

Rapid mixing of the down-up walk on matchings of a fixed size

Vishesh Jain, Clayton Mizgerd

Let $G = (V, E)$ be a graph on $n$ vertices and let $m^{*} (G)$ denote the size of a maximum matching in $G$ . We show that for any $δ > 0$ and for any $1 \leq k \leq (1 - δ) m^{*} (G)$ , the d…

math.CO2024

An explicit economical additive basis

Vishesh Jain, Huy Tuan Pham, Mehtaab Sawhney +1

We present an explicit subset $A \subseteq N = {0, 1, \dots}$ such that $A + A = N$ and for all $ε > 0$ , \[\lim_{N\to \infty}\frac{\big|\big\{(n_1,n_2):…

math.PR2022★ 1 cited

Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong

Let $G = (V, E)$ be an undirected graph with maximum degree $Δ$ and vertex conductance $Ψ^{*} (G)$ . We show that there exists a symmetric, stochastic matrix $P$ , with off-diagonal entr…

A general counting and sampling Lovász local lemma

A deterministic (1+ε)n approximation for the permanent of a nonnegative matrix

Optimal girth-dependent bounds for the Bethe approximation of the permanent

The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

On graphically local versions of metric embeddings

Total variation cutoff for Kac's walk on the sphere

The online monotone array completion problem

On the maximum density of r-graphs in which every (r+1)-set spans 0 or 2 edges

The size of the spanning-tree spectrum of simple graphs

Thinned Quantile Shares are Universally Feasible

Entropic independence via sparse localization

Equality in Fill's spectral gap problem

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

The random graph process is globally synchronizing

Hitting time mixing for the random transposition walk

Rapid mixing of the down-up walk on matchings of a fixed size

An explicit economical additive basis

Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

A deterministic $(1 + ε)^{n}$ approximation for the permanent of a nonnegative matrix

On the maximum density of $r$ -graphs in which every $(r + 1)$ -set spans $0$ or $2$ edges