A note on exact external information complexity
In the authors' words
We study the prior-free zero-error private-coin external information complexity of finite two-party functions, with correctness on every input. An elementary rectangle/entropy argument gives . A complete classification of Boolean matrices leaves, up to input permutations and output complementation, only the two-overlapping-rectangles function without an exact value. An entropy potential and a finite rational protocol give . We also determine its deterministic external information and zero-error communication costs. A separate product-prior certificate and internal-information additivity yield , strictly exceeding the fractional-cover rate .
Main resultLimitation the authors admit
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.