A note on exact external information complexity
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.