4 papers
Explicit Constant-Alphabet Subspace Design Codes
Rohan Goyal, Venkatesan Guruswami, Jun-Ting Hsieh
The subspace design property for additive codes is a higher-dimensional generalization of the minimum distance property. As shown recently by Brakensiek, Chen, Dhar and Zhang, it i…
Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
Rohan Goyal, Venkatesan Guruswami
List recovery of error-correcting codes has emerged as a fundamental notion with broad applications across coding theory and theoretical computer science. Folded Reed-Solomon (FRS)…
Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
Rohan Goyal, Prahladh Harsha, Mrinal Kumar +1
A recent work of Goyal, Harsha, Kumar and Shankar gave nearly linear time algorithms for the list decoding of Folded Reed-Solomon codes (FRS) and univariate multiplicity codes up t…
Efficiently Batching Unambiguous Interactive Proofs
Bonnie Berger, Rohan Goyal, Matthew M. Hong +1
We show that if a language admits a public-coin unambiguous interactive proof (UIP) with round complexity , where bits are communicated per round, then the batch lang…