Paper recorded by Signals 4 on 2026-11-03 in cs.LG. Abstract reproduced from arXiv; link to the original below.
Published 2026-11-03 on arXiv · recorded by Signals 4 on 2026-11-04
Category: cs.LG · 机器学习 · first seen 2026-11-04
We prove a broad learning-theoretic generalization of the celebrated hardcore lemma concerning the average-case complexity of computing a Boolean function (Impagliazzo, 1995). Our starting point is the observation that the classic notion of a hardcore measure, which reweights a function's input distribution, is equivalent to an input-dependent masking channel that injects randomness into the funct