22 citations · 24 across the 6 of their papers we have counts for
6 papers
A Criterion for Decoding on the BSC
Anup Rao, Oscar Sprumont
We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive codes and Reed-Muller codes.…
Anti-concentration and the Exact Gap-Hamming Problem
Anup Rao, Amir Yehudayoff
We prove anti-concentration bounds for the inner product of two independent random vectors, and use these bounds to prove lower bounds in communication complexity. We show that if…
Tight bounds on the Fourier growth of bounded functions on the hypercube
Siddharth Iyer, Anup Rao, Victor Reis +2
We give tight bounds on the degree homogenous parts of a bounded function on the cube. We show that if has degree , then…
Optimal Space and Time for Streaming Pattern Matching
Tung Mai, Anup Rao, Ryan A. Rossi +1
In this work, we study longest common substring, pattern matching, and wildcard pattern matching in the asymmetric streaming model. In this streaming model, we have random access t…
An Elementary Exposition of Pisier's Inequality
Siddharth Iyer, Anup Rao, Victor Reis +2
Pisier's inequality is central in the study of normed spaces and has important applications in geometry. We provide an elementary proof of this inequality, which avoids some non-co…
Information Equals Amortized Communication
Mark Braverman, Anup Rao
We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the…