Measuring communication complexity using instance complexity with oracles

Details Measuring communication complexity using instance complexity with oracles Measuring communication complexity using instance complexity with oracles

2009-01-19

arxiv.org/abs/0901.2906v1

Computer Science

Computational Complexity

Scientific paper

We 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}))$.

Affiliated with

Also associated with

No associations

Rating

Measuring communication complexity using instance complexity with oracles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Measuring communication complexity using instance complexity with oracles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Measuring communication complexity using instance complexity with oracles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-567066