Showing cs.ITShow all
2 papers · 1 filter
cs.IT2016
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,…
cs.IT2012
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/ε)…