Vishesh Jain

activity

20132023

most citedSingularity of random symmetric matrices -- a combinatorial approach to improved bounds

25 citations · 70 across the 30 of their papers we have counts for

collaborators

46 papers

math.PR2023

Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses

Nima Anari, Vishesh Jain, Frederic Koehler +2

We study Glauber dynamics for sampling from discrete distributions $μ$ on the hypercube ${\pm 1}^{n}$ . Recently, techniques based on spectral independence have successfully yielded…

math.CO2023

The binomial random graph is a bad inducer

Vishesh Jain, Marcus Michelen, Fan Wei

For a finite graph $F$ and a value $p \in [0, 1]$ , let $I (F, p)$ denote the largest $y$ for which there is a sequence of graphs of edge density approaching $p$ so that the induced $F…

cs.DS2023

Optimal mixing of the down-up walk on independent sets of a given size

Vishesh Jain, Marcus Michelen, Huy Tuan Pham +1

Let $G$ be a graph on $n$ vertices of maximum degree $Δ$ . We show that, for any $δ > 0$ , the down-up walk on independent sets of size $k \leq (1 - δ) α_{c} (Δ) n$ mixes in time $O_{Δ,δ}(k\…

math.CO2022★ 1 cited

Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings

Vishesh Jain, Huy Tuan Pham

We show that the threshold for the binomial random $3$ -partite, $3$ -uniform hypergraph $G^{3} ((n, n, n), p)$ to contain a Latin square is $Θ (lo g n / n)$ . We also prove analogous resul…

cs.DS2022

Spencer's theorem in nearly input-sparsity time

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

A celebrated theorem of Spencer states that for every set system $S_{1}, \dots, S_{m} \subseteq [n]$ , there is a coloring of the ground set with ${\pm 1}$ with discrepancy $O(\sqrt{n\…

math.PR2022

Optimal minimization of the covariance loss

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $X$ be a random vector valued in $R^{m}$ such that $∥ X ∥_{2} \leq 1$ almost surely. For every $k \geq 3$ , we show that there exists a sigma algebra $F$ generat…

cs.DS2021

Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities

Nima Anari, Vishesh Jain, Frederic Koehler +2

We introduce a framework for obtaining tight mixing times for Markov chains based on what we call restricted modified log-Sobolev inequalities. Modified log-Sobolev inequalities (M…

cs.DS2021

Approximate counting and sampling via local central limit theorems

Vishesh Jain, Will Perkins, Ashwin Sah +1

We give an FPTAS for computing the number of matchings of size $k$ in a graph $G$ of maximum degree $Δ$ on $n$ vertices, for all $k \leq (1 - δ) m^{*} (G)$ , where $δ > 0$ is fixed and $m^*(…

math.PR2021

Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial

Asaf Ferber, Vishesh Jain, Ashwin Sah +1

Conditional on the extended Riemann hypothesis, we show that with high probability, the characteristic polynomial of a random symmetric ${\pm 1}$ -matrix is irreducible. This addr…

cs.DS2021★ 1 cited

Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models

Nima Anari, Vishesh Jain, Frederic Koehler +2

We introduce a notion called entropic independence that is an entropic analog of spectral notions of high-dimensional expansion. Informally, entropic independence of a background d…

cs.DS2021

Spectral independence, coupling with the stationary distribution, and the spectral gap of the Glauber dynamics

Vishesh Jain, Huy Tuan Pham, Thuy Duong Vuong

We present a new lower bound on the spectral gap of the Glauber dynamics for the Gibbs distribution of a spectrally independent $q$ -spin system on a graph $G = (V, E)$ with maximum…

math.PR2021

Rank deficiency of random matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $M_{n}$ be a random $n \times n$ matrix with i.i.d. $Bernoulli (1/2)$ entries. We show that for fixed $k \geq 1$ , \[\lim_{n\to \infty}\frac{1}{n}\log_2\mathbb{P}[\text{corank…

cs.DS2021★ 6 cited

On the sampling Lovász Local Lemma for atomic constraint satisfaction problems

Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong

We study the problem of sampling an approximately uniformly random satisfying assignment for atomic constraint satisfaction problems i.e. where each constraint is violated by only…

math.CO2021

Anticoncentration versus the number of subset sums

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $w = (w_{1}, \dots, w_{n}) \in R^{n}$ . We show that for any $n^{- 2} \leq ε \leq 1$ , if \[\#\{\vecξ \in \{0,1\}^{n}: \langle \vecξ, \vec{w} \rangle = τ\} \ge 2^{-εn}\cdot 2…

math.PR2020

Optimal and algorithmic norm regularization of random matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $A$ be an $n \times n$ random matrix whose entries are i.i.d. with mean $0$ and variance $1$ . We present a deterministic polynomial time algorithm which, with probability at lea…

cs.DS2020

Towards the sampling Lovász Local Lemma

Vishesh Jain, Huy Tuan Pham, Thuy Duong Vuong

Let $Φ = (V, C)$ be a constraint satisfaction problem on variables $v_{1}, \dots, v_{n}$ such that each constraint depends on at most $k$ variables and such that each variable…

math.PR2020

On the smallest singular value of symmetric random matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

We show that for an $n \times n$ random symmetric matrix $A_{n}$ , whose entries on and above the diagonal are independent copies of a sub-Gaussian random variable $ξ$ with mean $0$ an…

math.PR2020

Singularity of discrete random matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $ξ$ be a non-constant real-valued random variable with finite support, and let $M_{n} (ξ)$ denote an $n \times n$ random matrix with entries that are independent copies of $ξ$ . F…

math.PR2020★ 2 cited

Sharp invertibility of random Bernoulli matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $p \in (0, 1/2)$ be fixed, and let $B_{n} (p)$ be an $n \times n$ random matrix with i.i.d. Bernoulli random variables with mean $p$ . We show that for all $t \geq 0$ , \[\mathbb{P}[s_…

math.PR2020

On the smoothed analysis of the smallest singular value with discrete noise

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $A$ be an $n \times n$ real matrix, and let $M$ be an $n \times n$ random matrix whose entries are i.i.d sub-Gaussian random variables with mean $0$ and variance $1$ . We make two…

math.PR2020

The smallest singular value of dense random regular digraphs

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $A$ be the adjacency matrix of a uniformly random $d$ -regular digraph on $n$ vertices, and suppose that $min (d, n - d) \geq λn$ . We show that for any $κ \geq 0$ , \[\mathbb{P}[s_n(A)…

math.PR2020★ 3 cited

Circular Law for Random Block Band Matrices with Genuinely Sublinear Bandwidth

Vishesh Jain, Indrajit Jana, Kyle Luh +1

We prove the circular law for a class of non-Hermitian random block band matrices with genuinely sublinear bandwidth. Namely, we show there exists $τ \in (0, 1)$ so that if the bandw…

cs.DS2020

Perfectly Sampling $k \geq (8/3 + o (1)) Δ$ -Colorings in Graphs

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

We present a randomized algorithm which takes as input an undirected graph $G$ on $n$ vertices with maximum degree $Δ$ , and a number of colors $k \geq (8/3 + o_{Δ} (1)) Δ$ , and returns…

math.PR2020

Universality and least singular values of random matrix products: a simplified approach

Rohit Chaudhuri, Vishesh Jain, Natesh S. Pillai

In this note, we show how to provide sharp control on the least singular value of a certain translated linearization matrix arising in the study of the local universality of produc…

Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses

The binomial random graph is a bad inducer

Optimal mixing of the down-up walk on independent sets of a given size

Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings

Spencer's theorem in nearly input-sparsity time

Optimal minimization of the covariance loss

Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities

Approximate counting and sampling via local central limit theorems

Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial

Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models

Spectral independence, coupling with the stationary distribution, and the spectral gap of the Glauber dynamics

Rank deficiency of random matrices

On the sampling Lovász Local Lemma for atomic constraint satisfaction problems

Anticoncentration versus the number of subset sums

Optimal and algorithmic norm regularization of random matrices

Towards the sampling Lovász Local Lemma

On the smallest singular value of symmetric random matrices

Singularity of discrete random matrices

Sharp invertibility of random Bernoulli matrices

On the smoothed analysis of the smallest singular value with discrete noise

The smallest singular value of dense random regular digraphs

Circular Law for Random Block Band Matrices with Genuinely Sublinear Bandwidth

Perfectly Sampling k≥(8/3+o(1))Δ-Colorings in Graphs

Universality and least singular values of random matrix products: a simplified approach

Perfectly Sampling $k \geq (8/3 + o (1)) Δ$ -Colorings in Graphs