Round Elimination using Triangular Discrimination
summary
Shows that replacing round elimination with an analysis of distributions using triangular discrimination (Delta) yields stronger, practical lower bounds on interactive rounds. Uses KL subadditivity on a high-entropy Boolean cube instance with KL distance K to get per-coordinate KL ≈ K/n, then converts to operational testing error without the usual Pinsker square root. The key claims: Delta is between L1 and KL, it preserves data processing, and it gives no square root loss, improving quantitative parameters for round elimination via distributional distance.
AI-written summary · about