Comparing computational entropies below majority (or: When is the dense model theorem false?)
summary
Shows explicit separations proving the dense model theorem false below majority: constructions of delta-dense distributions that are pseudorandom for small circuits yet have no delta-dense epsilon-model unless tests can compute majority, so polynomial dependence epsilon' = poly(epsilon,delta) requires majority. Produces counterexamples in AC0 and for low-degree polynomials, and thus gives counterexamples to the hardcore lemma below majority. Techniques include LP duality, Chernoff aggregation, biased-set packing and coin‑problem concentration bounds.
AI-written summary · about