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

Showing 2020Show all

14 papers · 1 filter

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…

math.PR2020

A note on the universality of ESDs of inhomogeneous random matrices

Vishesh Jain, Sandeep Silwal

In this short note, we extend the celebrated results of Tao and Vu, and Krishnapur on the universality of empirical spectral distributions to a wide class of inhomogeneous complex…

math.FA2020

On the real Davies' conjecture

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

We show that every matrix $A \in R^{n \times n}$ is at least $δ$ $∥ A ∥$ -close to a real matrix $A + E \in R^{n \times n}$ whose eigenvectors have condition number at…

cs.DS2020

Fast and memory-optimal dimension reduction using Kac's walk

Vishesh Jain, Natesh S. Pillai, Ashwin Sah +2

In this work, we analyze dimension reduction algorithms based on the Kac walk and discrete variants. (1) For $n$ points in $R^{d}$ , we design an optimal Johnson-Lindenstra…

math.CO2020★ 1 cited

The probability of selecting $k$ edge-disjoint Hamilton cycles in the complete graph

Asaf Ferber, Kaarel Haenni, Vishesh Jain

Let $H_{1}, \dots, H_{k}$ be Hamilton cycles in $K_{n}$ , chosen independently and uniformly at random. We show, for $k = o (n^{1/100})$ , that the probability of $H_{1}, \dots, H_{k}$ being edge-d…

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

A note on the universality of ESDs of inhomogeneous random matrices

On the real Davies' conjecture

Fast and memory-optimal dimension reduction using Kac's walk

The probability of selecting k edge-disjoint Hamilton cycles in the complete graph

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

The probability of selecting $k$ edge-disjoint Hamilton cycles in the complete graph