Vinayak M. Kumar

collaborators

4 papers

cs.IT2026

List Decoding, Linear Hashing, and Furstenberg over $F_{q}$

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 $F_{q}$ . 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) $C : {0, 1}^{k} \to {0, 1}^{n}$ is an error-correcting code that allows one to recover any bit of the original message with good probability while…

cs.CC2025

Most Juntas Saturate the Hardcore Lemma

Vinayak M. Kumar

Consider a function that is mildly hard for size- $s$ circuits. For sufficiently large $s$ , Impagliazzo's hardcore lemma guarantees a constant-density subset of inputs on which the…

cs.DS2025

Linear Hashing Is Optimal

Michael Jaber, Vinayak M. Kumar, David Zuckerman

We prove that hashing $n$ balls into $n$ bins via a random matrix over $F_{2}$ yields expected maximum load $O (lo g n / lo g lo g n)$ . This matches the expected maximum load…

List Decoding, Linear Hashing, and Furstenberg over Fq​

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes

Most Juntas Saturate the Hardcore Lemma

Linear Hashing Is Optimal

List Decoding, Linear Hashing, and Furstenberg over $F_{q}$