Source author record

Vishesh Jain

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math.CO Data Structures and Algorithms math.NA Numerical Analysis Information Theory math.AP math.FA math.IT math.OC math.SP

Catalog footprint

Research overview

15works

11topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

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 entries supported on $E$ , whose spectral gap $γ^*(P)$ satisfies $Ψ^*(G)^{2}/\logΔ\lesssim γ^*(P) \lesssim Ψ^*(G).$ Our bound is optimal under the Small Set Expansion Hypothesis, and answers a question of Olesker-Taylor and Zanetti, who obtained such a result with $\logΔ$ replaced by $\log|V|$ . In order to obtain our result, we show how to embed a negative-type semi-metric $d$ defined on $V$ into a negative-type semi-metric $d'$ supported in $\mathbb{R}^{O(\logΔ)}$ , such that the (fractional) matching number of the weighted graph $(V,E,d)$ is approximately equal to that of $(V,E,d')$ .

preprint2022arXiv

Optimal minimization of the covariance loss

Let $X$ be a random vector valued in $\mathbb{R}^{m}$ such that $\|X\|_{2} \le 1$ almost surely. For every $k\ge 3$ , we show that there exists a sigma algebra $\mathcal{F}$ generated by a partition of $\mathbb{R}^{m}$ into $k$ sets such that $\|\operatorname{Cov}(X) - \operatorname{Cov}(\mathbb{E}[X\mid\mathcal{F}]) \|_{\mathrm{F}} \lesssim \frac{1}{\sqrt{\log{k}}}.$ This is optimal up to the implicit constant and improves on a previous bound due to Boedihardjo, Strohmer, and Vershynin. Our proof provides an efficient algorithm for constructing $\mathcal{F}$ and leads to improved accuracy guarantees for $k$ -anonymous or differentially private synthetic data. We also establish a connection between the above problem of minimizing the covariance loss and the pinning lemma from statistical physics, providing an alternate (and much simpler) algorithmic proof in the important case when $X \in \{\pm 1\}^m/\sqrt{m}$ almost surely.

preprint2022arXiv

Spencer's theorem in nearly input-sparsity time

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\log(m/n+2)})$ . We provide an algorithm to find such a coloring in near input-sparsity time $\tilde{O}(n+\sum_{i=1}^{m}|S_i|)$ . A key ingredient in our work, which may be of independent interest, is a novel width reduction technique for solving linear programs, not of covering/packing type, in near input-sparsity time using the multiplicative weights update method.

preprint2021arXiv

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

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 one assignment to its variables. Let $p$ denote the maximum probability of violation of any constraint and let $Δ$ denote the maximum degree of the line graph of the constraints. Our main result is a nearly-linear (in the number of variables) time algorithm for this problem, which is valid in a Lovász local lemma type regime that is considerably less restrictive compared to previous works. In particular, we provide sampling algorithms for the uniform distribution on: (1) $q$ -colorings of $k$ -uniform hypergraphs with $Δ\lesssim q^{(k-4)/3 + o_{q}(1)}.$ The exponent $1/3$ improves the previously best-known $1/7$ in the case $q, Δ= O(1)$ [Jain, Pham, Vuong; arXiv, 2020] and $1/9$ in the general case [Feng, He, Yin; STOC 2021]. (2) Satisfying assignments of Boolean $k$ -CNF formulas with $Δ\lesssim 2^{k/5.741}.$ The constant $5.741$ in the exponent improves the previously best-known $7$ in the case $k = O(1)$ [Jain, Pham, Vuong; arXiv, 2020] and $13$ in the general case [Feng, He, Yin; STOC 2021]. (3) Satisfying assignments of general atomic constraint satisfaction problems with $p\cdot Δ^{7.043} \lesssim 1.$ The constant $7.043$ improves upon the previously best-known constant of $350$ [Feng, He, Yin; STOC 2021]. At the heart of our analysis is a novel information-percolation type argument for showing the rapid mixing of the Glauber dynamics for a carefully constructed projection of the uniform distribution on satisfying assignments. Notably, there is no natural partial order on the space, and we believe that the techniques developed for the analysis may be of independent interest.

preprint2021arXiv

Rank deficiency of random matrices

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

preprint2020arXiv

A note on the universality of ESDs of inhomogeneous random matrices

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 random matrices, by showing that a technical and hard-to-verify Fourier domination assumption may be replaced simply by a natural uniform anti-concentration assumption. Along the way, we show that inhomogeneous complex random matrices, whose expected squared Hilbert-Schmidt norm is quadratic in the dimension, and whose entries (after symmetrization) are uniformly anti-concentrated at $0$ and infinity, typically have smallest singular value $Ω(n^{-1/2})$ . The rate $n^{-1/2}$ is sharp, and closes a gap in the literature. Our proofs closely follow recent works of Livshyts, and Livshyts, Tikhomirov, and Vershynin on inhomogeneous real random matrices. The new ingredient is a couple of anti-concentration inequalities for sums of independent, but not necessarily identically distributed, complex random variables, which may also be useful in other contexts.

preprint2020arXiv

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

In this work, we analyze dimension reduction algorithms based on the Kac walk and discrete variants. (1) For $n$ points in $\mathbb{R}^{d}$ , we design an optimal Johnson-Lindenstrauss (JL) transform based on the Kac walk which can be applied to any vector in time $O(d\log{d})$ for essentially the same restriction on $n$ as in the best-known transforms due to Ailon and Liberty [SODA, 2008], and Bamberger and Krahmer [arXiv, 2017]. Our algorithm is memory-optimal, and outperforms existing algorithms in regimes when $n$ is sufficiently large and the distortion parameter is sufficiently small. In particular, this confirms a conjecture of Ailon and Chazelle [STOC, 2006] in a stronger form. (2) The same construction gives a simple transform with optimal Restricted Isometry Property (RIP) which can be applied in time $O(d\log{d})$ for essentially the same range of sparsity as in the best-known such transform due to Ailon and Rauhut [Discrete Comput. Geom., 2014]. (3) We show that by fixing the angle in the Kac walk to be $π/4$ throughout, one obtains optimal JL and RIP transforms with almost the same running time, thereby confirming -- up to a $\log\log{d}$ factor -- a conjecture of Avron, Maymounkov, and Toledo [SIAM J. Sci. Comput., 2010]. Our moment-based analysis of this modification of the Kac walk may also be of independent interest.

preprint2020arXiv

On the real Davies' conjecture

We show that every matrix $A \in \mathbb{R}^{n\times n}$ is at least $δ$ $\|A\|$ -close to a real matrix $A+E \in \mathbb{R}^{n\times n}$ whose eigenvectors have condition number at most $\tilde{O}_{n}(δ^{-1})$ . In fact, we prove that, with high probability, taking $E$ to be a sufficiently small multiple of an i.i.d. real sub-Gaussian matrix of bounded density suffices. This essentially confirms a speculation of Davies, and of Banks, Kulkarni, Mukherjee, and Srivastava, who recently proved such a result for i.i.d. complex Gaussian matrices. Along the way, we also prove non-asymptotic estimates on the minimum possible distance between any two eigenvalues of a random matrix whose entries have arbitrary means; this part of our paper may be of independent interest.

preprint2020arXiv

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

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 contributions to the study of $s_n(A+M)$ , the smallest singular value of $A+M$ . (1) We show that for all $ε\geq 0$ , $\mathbb{P}[s_n(A + M) \leq ε] = O(ε\sqrt{n}) + 2e^{-Ω(n)},$ provided only that $A$ has $Ω(n)$ singular values which are $O(\sqrt{n})$ . This extends a well-known result of Rudelson and Vershynin, which requires all singular values of $A$ to be $O(\sqrt{n})$ . (2) We show that any bound of the form $\sup_{\|{A}\|\leq n^{C_1}}\mathbb{P}[s_n(A+M)\leq n^{-C_3}] \leq n^{-C_2}$ must have $C_3 = Ω(C_1 \sqrt{C_2})$ . This complements a result of Tao and Vu, who proved such a bound with $C_3 = O(C_1C_2 + C_1 + 1)$ , and counters their speculation of possibly taking $C_3 = O(C_1 + C_2)$ .

preprint2020arXiv

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

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 -- in expected time $\tilde{O}(nΔ^{2}\log{k})$ -- a proper $k$ -coloring of $G$ distributed perfectly uniformly on the set of all proper $k$ -colorings of $G$ . Notably, our sampler breaks the barrier at $k = 3Δ$ encountered in recent work of Bhandari and Chakraborty [STOC 2020]. We also sketch how to modify our methods to relax the restriction on $k$ to $k \geq (8/3 - ε_0)Δ$ for an absolute constant $ε_0 > 0$ . As in the work of Bhandari and Chakraborty, and the pioneering work of Huber [STOC 1998], our sampler is based on Coupling from the Past [Propp&Wilson, Random Struct. Algorithms, 1995] and the bounding chain method [Huber, STOC 1998; Häggström&Nelander, Scand. J. Statist., 1999]. Our innovations include a novel bounding chain routine inspired by Jerrum's analysis of the Glauber dynamics [Random Struct. Algorithms, 1995], as well as a preconditioning routine for bounding chains which uses the algorithmic Lovász Local Lemma [Moser&Tardos, J.ACM, 2010].

preprint2020arXiv

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

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-disjoint is $(1+o(1))e^{-2\binom{k}{2}}$ . This extends a corresponding estimate obtained by Robbins in the case $k=2$ .

preprint2020arXiv

The smallest singular value of dense random regular digraphs

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)\leqκ]\leq C_λκ\sqrt{n}+2e^{-c_λn}.$ Up to the constants $C_λ, c_λ> 0$ , our bound matches optimal bounds for $n\times n$ random matrices, each of whose entries is an i.i.d $\text{Ber}(d/n)$ random variable. The special case $κ= 0$ of our result confirms a conjecture of Cook regarding the probability of singularity of dense random regular digraphs.

preprint2020arXiv

The strong circular law: a combinatorial view

Let $N_n$ be an $n\times n$ complex random matrix, each of whose entries is an independent copy of a centered complex random variable $z$ with finite non-zero variance $σ^{2}$ . The strong circular law, proved by Tao and Vu, states that almost surely, as $n\to \infty$ , the empirical spectral distribution of $N_n/(σ\sqrt{n})$ converges to the uniform distribution on the unit disc in $\mathbb{C}$ . A crucial ingredient in the proof of Tao and Vu, which uses deep ideas from additive combinatorics, is controlling the lower tail of the least singular value of the random matrix $xI - N_{n}/(σ\sqrt{n})$ (where $x\in \mathbb{C}$ is fixed) with failure probability that is inverse polynomial. In this paper, using a simple and novel approach (in particular, not using tools from additive combinatorics or any net arguments), we show that for any fixed matrix $M$ with operator norm at most $n^{0.51}$ and for all $η\geq 0$ , $\Pr\left(s_n(M+N_n) \leq η\right) \lesssim n^{C}η+ \exp(-n^{c}),$ where $s_n(M+N_n)$ is the least singular value of $M+N_n$ and $C,c$ are absolute constants. Our result is optimal up to the constants $C,c$ and the inverse exponential-type error rate improves upon the inverse polynomial error rate due to Tao and Vu. During the course of our proof, we extend the solution of the counting problem in inverse Littlewood-Offord theory, recently isolated by the author along with Ferber, Luh, and Samotij, from Rademacher variables to general complex random variables. This significantly improves on estimates for this problem obtained using the optimal inverse Littlewood-Offord theorem of Nguyen and Vu, and may be of independent interest.

preprint2020arXiv

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

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 products of independent random matrices. This problem was first considered in a recent work of Koppel, O'Rourke, and Vu, and compared to their work, our proof is substantially simpler and established in much greater generality . In particular, we only assume that the entries of the ensemble are centered, and have second and fourth moments uniformly bounded away from $0$ and infinity, whereas previous work assumed a uniform subgaussian decay condition and that the entries within each factor of the product are identically distributed. A consequence of our least singular value bound is that the four moment matching universality results for the products of independent random matrices, recently obtained by Koppel, O'Rourke, and Vu, hold under much weaker hypotheses. Our proof technique is also of independent interest in the study of structured sparse matrices.

preprint2014arXiv

On discontinuity of planar optimal transport maps

Consider two bounded domains $Ω$ and $Λ$ in $\mathbb{R}^{2}$ , and two sufficiently regular probability measures $μ$ and $ν$ supported on them. By Brenier's theorem, there exists a unique transportation map $T$ satisfying $T_\#μ=ν$ and minimizing the quadratic cost $\int_{\mathbb{R}^{n}}|T(x)-x|^{2}dμ(x)$ . Furthermore, by Caffarelli's regularity theory for the real Monge--Ampère equations, if $Λ$ is convex, $T$ is continuous. We study the reverse problem, namely, when is $T$ discontinuous if $Λ$ fails to be convex? We prove a result guaranteeing the discontinuity of $T$ in terms of the geometries of $Λ$ and $Ω$ in the two-dimensional case. The main idea is to use tools of convex analysis and the extrinsic geometry of $\partialΛ$ to distinguish between Brenier and Alexandrov weak solutions of the Monge--Ampère equation. We also use this approach to give a new proof of a result due to Wolfson and Urbas. We conclude by revisiting an example of Caffarelli, giving a detailed study of a discontinuous map between two explicit domains, and determining precisely where the discontinuities occur.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Vishesh Jain

Research overview

Is this your work?

15 publications

Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Optimal minimization of the covariance loss

Spencer's theorem in nearly input-sparsity time

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

Rank deficiency of random matrices

A note on the universality of ESDs of inhomogeneous random matrices

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

On the real Davies' conjecture

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

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

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

The smallest singular value of dense random regular digraphs

The strong circular law: a combinatorial view

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

On discontinuity of planar optimal transport maps

See the researcher in context

Building this map preview

Vishesh Jain

Research overview

Is this your work?

15 publications

Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Optimal minimization of the covariance loss

Spencer's theorem in nearly input-sparsity time

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

Rank deficiency of random matrices

A note on the universality of ESDs of inhomogeneous random matrices

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

On the real Davies' conjecture

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

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

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

The smallest singular value of dense random regular digraphs

The strong circular law: a combinatorial view

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

On discontinuity of planar optimal transport maps

See the researcher in context

Building this map preview

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

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