4 papers
Bridging the Capacity Gap Between Interactive and One-Way Communication
Bernhard Haeupler, Ameya Velingker
We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise. Recently,…
Approximating Nearest Neighbor Distances
Michael B. Cohen, Brittany Terese Fasy, Gary L. Miller +3
Several researchers proposed using non-Euclidean metrics on point sets in Euclidean space for clustering noisy data. Almost always, a distance function is desired that recognizes t…
A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs
Gary L. Miller, Donald R. Sheehy, Ameya Velingker
We present a new algorithm that produces a well-spaced superset of points conforming to a given input set in any dimension with guaranteed optimal output size. We also provide an a…
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
We prove that a random linear code over F_q, with probability arbitrarily close to 1, is list decodable at radius (1-1/q-ε) with list size L=O(1/ε^2) and rate R=Ω_q(ε^2/(log^3(1/ε)…