Measuring communication complexity using instance complexity with oracles

Simple item page
dc.creatorMatos, Armando
dc.creatorTeixeira, Andreia
dc.creatorSouto, Andre
dc.date2009-01-19
dc.date.accessioned2026-07-07T12:31:39Z
dc.date.available2026-07-07T12:31:39Z
dc.descriptionWe establish a connection between non-deterministic communication complexity and instance complexity, a measure of information based on algorithmic entropy. Let $\overline{x}$, $\overline{y}$ and $Y_1(\overline{x})$ be respectively the input known by Alice, the input known by Bob, and the set of all values of $y$ such that $f(\overline{x},y)=1$; a string is a witness of the non-deterministic communication protocol iff it is a program $p$ that "corresponds exactly" to the instance complexity $\ic^{f,t}(\overline{y}:Y_1(\overline{x}))$.
dc.identifierhttps://arxiv.org/abs/0901.2906
dc.identifierhttp://arxiv.org/abs/0901.2906
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/216520
dc.subjectComputational Complexity
dc.titleMeasuring communication complexity using instance complexity with oracles
dc.typetext

Files

Collections

arXiv