Mehtaab Sawhney

works on

coding theory 1 covering codes 1 packing bounds 1 q-ary codes 1 singleton bound 1 sphere-packing bound 1

From the 1 of 13 linked papers with an AI index.

activity

20172020

collaborators

13 papers

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…

cs.DS2020

Discrepancy Minimization via a Self-Balancing Walk

Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney

We study discrepancy minimization for vectors in $R^{n}$ under various settings. The main result is the analysis of a new simple random process in multiple dimensions throug…

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…

math.CO2019

Bounded Degree Spanners of the Hypercube

Rajko Nenadov, Mehtaab Sawhney, Benny Sudakov +1

In this short note we study two questions about the existence of subgraphs of the hypercube $Q_{n}$ with certain properties. The first question, due to Erdős--Hamburger--Pippert--Wea…

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

Discrepancy Minimization via a Self-Balancing Walk

On the real Davies' conjecture

Bounded Degree Spanners of the Hypercube

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