Shravas Rao

activity

20122021

most citedImproved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices

3 citations · 4 across the 4 of their papers we have counts for

collaborators

7 papers

math.CO2021

The Fourier Transform of Restrictions of Functions on the Slice

Shravas Rao

This paper considers the Fourier transform over the slice of the Boolean hypercube. We prove a relationship between the Fourier coefficients of a function over the slice, and the F…

quant-ph2020

Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem

Scott Aaronson, Shalev Ben-David, Robin Kothari +2

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$ , $∙ deg (f) = O (deg (f)^{2})$ : The degree of…

math.PR2019

Concentration of Markov chains with bounded moments

Assaf Naor, Shravas Rao, Oded Regev

Let ${W_{t}}_{t = 1}^{\infty}$ be a finite state stationary Markov chain, and suppose that $f$ is a real-valued function on the state space. If $f$ is bounded, then Gillman's expande…

math.CO2019

The Littlewood-Offord Problem for Markov Chains

Shravas Rao

The celebrated Littlewood-Offord problem asks for an upper bound on the probability that the random variable $ε_{1} v_{1} + \dots + ε_{n} v_{n}$ lies in the Euclidean unit ball, where $ε_…

cs.IT2019★ 3 cited

Improved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices

Shravas Rao

Let $A$ be an $N \times N$ Fourier matrix over $F_{p}^{l o g N / l o g p}$ for some prime $p$ . We improve upon known lower bounds for the number of rows of $A$ that must be sa…

math.PR2018

A Hoeffding inequality for Markov chains

Shravas Rao

We prove deviation bounds for the random variable $\sum_{i = 1}^{n} f_{i} (Y_{i})$ in which ${Y_{i}}_{i = 1}^{\infty}$ is a Markov chain with stationary distribution and state space $[N]$ ,…