3 citations · 8 across the 11 of their papers we have counts for
16 papers
Noisy Quantum Query Complexity via Fractional Block Sensitivity
Mehil Agarwal, Shravas Rao, Fang Song
We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ($\oper…
Towards a Banach Space Chernoff Bound for Markov Chains via Chaining Arguments
Shravas Rao
Let be a stationary reversible Markov chain with state space , let be a real-valued Banach space and let $f_1, \ldots, f_n: [N] \ri…
Expanderizing Higher Order Random Walks
Vedat Levi Alev, Shravas Rao
We study a variant of the down-up and up-down walks over an -partite simplicial complex, which we call expanderized higher order random walks -- where the sequence of updated co…
Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
Shravas Rao
A matrix satisfies the restricted isometry property if is approximately equal to for all -sparse vectors . We give a c…
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…
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 , : The degree of…
Concentration of Markov chains with bounded moments
Assaf Naor, Shravas Rao, Oded Regev
Let be a finite state stationary Markov chain, and suppose that is a real-valued function on the state space. If is bounded, then Gillman's expande…
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 lies in the Euclidean unit ball, where $ε_…
Improved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices
Shravas Rao
Let be an Fourier matrix over for some prime . We improve upon known lower bounds for the number of rows of that must be sa…
An Improved Lower Bound for Sparse Reconstruction from Subsampled Walsh Matrices
Jarosław Błasiok, Patrick Lopatto, Kyle Luh +2
We give a short argument that yields a new lower bound on the number of subsampled rows from a bounded, orthonormal matrix necessary to form a matrix with the restricted isometry p…
A Hoeffding inequality for Markov chains
Shravas Rao
We prove deviation bounds for the random variable in which is a Markov chain with stationary distribution and state space ,…
A Sharp Tail Bound for the Expander Random Sampler
Shravas Rao, Oded Regev
Consider an expander graph in which a fraction of the vertices are marked. A random walk starts at a uniform vertex and at each step continues to a random neighbor. Gillman sho…
Arithmetic expanders and deviation bounds for random tensors
Jop Briët, Shravas Rao
We prove hypergraph variants of the celebrated Alon-Roichman theorem on spectral expansion of sparse random Cayley graphs. One of these variants implies that for every prime $p\geq…
Applications of -strongly regular distributions to Bayesian auctions
Richard Cole, Shravas Rao
Two classes of distributions that are widely used in the analysis of Bayesian auctions are the Monotone Hazard Rate (MHR) and Regular distributions. They can both be characterized…
On Lipschitz Bijections between Boolean Functions
Shravas Rao, Igor Shinkar
For two functions a mapping is said to be a $\textit{mapping from $fg$}$ if it is a bijection and for every…
Finding hitting times in various graphs
Shravas Rao
The hitting time, h_uv, of a random walk on a finite graph G, is the expected time for the walk to reach vertex v given that it started at vertex u. We present two methods of calcu…