Lower Bounds for Elimination via Weak Regularity
summary
Proves a quantitative lower bound for elimination: any distributional deterministic protocol for k independent copies must use at least log(1/discrepancy_mu(F)) − log K − O(log(1/ε) + 1) bits (so, for inner product this gives ≳ n/2 − log K). Proof uses a weak regularity condition on protocol rectangles, connects balanced splitting of outputs to discrepancy, and relies on lifting-like arguments. This rules out large savings over solving one instance (after avoiding trivial error 2^−k) and matches simple upper bounds like n − ½ log K up to constants.
AI-written summary · about