Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Most Juntas Saturate the Hardcore Lemma
Vinayak M. Kumar
Consider a function that is mildly hard for size- circuits. For sufficiently large , 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) is an error-correcting code that allows one to recover any bit of the original message with good probability while…