Ashwin Sah

activity

20182026

most citedDiagonal Ramsey via effective quasirandomness

6 citations · 11 across the 17 of their papers we have counts for

collaborators

Showing 2020Show all

8 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…

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

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)…

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.CO2020★ 6 cited

Diagonal Ramsey via effective quasirandomness

Ashwin Sah

We improve the upper bound for diagonal Ramsey numbers to \[R(k+1,k+1)\le\exp(-c(\log k)^2)\binom{2k}{k}\] for $k \geq 3$ . To do so, we build on a quasirandomness and induction frame…

Optimal and algorithmic norm regularization of random matrices

On the smallest singular value of symmetric random matrices

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

The smallest singular value of dense random regular digraphs

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

Diagonal Ramsey via effective quasirandomness

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