3 papers
cs.IT2026
List Decoding, Linear Hashing, and Furstenberg over
Vinayak M. Kumar, Geoffrey Mon
We give new bounds for list sizes of random linear codes at capacity, max loads of linear hash functions, and Furstenberg sets, over every finite field . 1. Random li…
cs.CC2025
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
Elena Grigorescu, Vinayak M. Kumar, Peter Manohar +1
A locally decodable code (LDC) is an error-correcting code that allows one to recover any bit of the original message with good probability while…
cs.CC2023
Relaxed Local Correctability from Local Testing
Vinayak M. Kumar, Geoffrey Mon
We construct the first asymptotically good relaxed locally correctable codes with polylogarithmic query complexity, bringing the upper bound polynomially close to the lower bound o…