Relative Discrepancy Does Not Separate Information and Communication Complexity
summary
Linear-program comparisons produce a concrete collapse: a change-of-variables maps relative discrepancy solutions to feasible points for the relaxed partition bound, and the relaxed partition bound lower-bounds information complexity in the non-distributional setting, so relative discrepancy never exceeds the information measure and cannot give a non-distributional separation. The argument uses primal/dual LPs and a zero-communication “abort” interpretation of the partition bound; it still leaves open why a tailored fixed distribution yields an exponential distributional gap.
AI-written summary · about
chapters (7)
- 0:00Start
- 0:20Whether Information Complexity Is Equal to Communication Complexity
- 2:46Internal Information Complexity
- 14:54The Discrepancy Method for Communication Complexity
- 15:36Communication Rectangle
- 17:14Partition Bound and the Relaxed Partition Bound
- 27:10Relaxed Partition Bound
related talks
01h 09mInformation Theory in Computational Complexity IV
01h 00mAverage-case Complexity for Polynomials, and All That
01h 01mCoding for Modern Distributed Storage Systems I
48mUnprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
56mEntropy, Capacity, and Counting
58mDichotomy Theorems for Counting Problems II
54mConstraints, Gadgets, and Invariants
51mAllender's Conjecture and its Impacts on Meta-Complexity