Vinayak M. Kumar

collaborators

3 papers

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…