Trading Information Complexity for Error
summary
Paper proves that allowing error ε reduces information cost for AND by Θ(H(ε)) and for Disjointness the per-instance cost drops by about H(ε) (matching earlier 0.4827·n constant asymptotics) while the distributional version can save more. Proofs combine a random-order one-sided protocol (stop on first intersection) for upper bounds and a long stability-based lower bound argument; general upper bound shows a gain of order H(ε) for every f but the general lower bound only reaches √H(ε), giving a separation between prior-free and distributional variants.
AI-written summary · about