pipette
ESEspañol

A note on exact external information complexity

Henning Wunderlich

Preprint

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.