From the 1 of 34 linked papers with an AI index.
1 citations · 1 across the 12 of their papers we have counts for
34 papers
Average-Radius List-Decodability of Random Linear Codes
Venkatesan Guruswami, Shilun Li, Mihir Singhal
We prove that for every prime power and every , a random -linear code of rate is -average-radius list-decodable…
Binary code rate bounds via classical--quantum channels
Omar Alrabiah, Venkatesan Guruswami
We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one…
Frequency Coding over Noisy Sampling
Bo-Yu Su, Hsin-Po Wang, Venkatesan Guruswami
DNA molecules are so small that it might be practical to use their frequency vectors to encode messages. More precisely, a sender can inject copies of the string CATCAT…
Inapproximability of Unique-Machine Precedence Scheduling for Unit-Length Jobs
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
The paper shows that scheduling unit-length jobs with unique-machine precedence constraints cannot be approximated within any constant factor, and under standard complexity assumpt…
Locality of Curve-Decoding and Improved Proximity Gaps
Rohan Goyal, Venkatesan Guruswami, Yihang Sun +1
Proximity gaps are a property of error correcting codes that arise in the study of Interactive Oracle Proofs (IOPs) and Succinct Non-interactive Arguments of Zero Knowledge (SNARKs…
Quantum Hierarchical Locally Recoverable Codes
Venkatesan Guruswami, Rutuja Kshirsagar, Pranav Trivedi
Quantum locally recoverable codes (QLRCs) have recently gained attention as a framework for achieving efficient quantum storage with local recovery capabilities. Analogous to their…