pipette
ENEnglish

A note on exact external information complexity

Henning Wunderlich

Preprint

En palabras de los autores

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 .

Resultado principalLimitación que admiten los autores

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.