From the 1 of 31 linked papers with an AI index.
31 papers
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…
On the Approximability of Parameterized Minimum Monotone Satisfying Assignment
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +1
The parameterized Minimum Monotone Satisfying Assignment (-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most . Th…