Vinayak M. Kumar

collaborators

3 papers

cs.CC2026

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.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.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…