Strategy in Ulam's Game and Tree Code Give Error-Resistant Protocols

Details Strategy in Ulam's Game and Tree Code Give Error-Resistant Protocols Strategy in Ulam's Game and Tree Code Give Error-Resistant Protocols

2004-10-18

arxiv.org/abs/cs/0410043v1

Computer Science

Distributed, Parallel, and Cluster Computing

10 pages, 2 figures

Scientific paper

We present a new approach to construction of protocols which are proof against communication errors. The construction is based on a generalization of the well known Ulam's game. We show equivalence between winning strategies in this game and robust protocols for multi-party computation. We do not give any complete theory. We want rather to describe a new fresh idea. We use a tree code defined by Schulman. The tree code is the most important part of the interactive version of Shannon's Coding Theorem proved by Schulman. He uses probabilistic argument for the existence of a tree code without giving any effective construction. We show another proof yielding a randomized construction which in contrary to his proof almost surely gives a good code. Moreover our construction uses much smaller alphabet.

Affiliated with

Also associated with

No associations

Rating

Strategy in Ulam's Game and Tree Code Give Error-Resistant Protocols 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 Strategy in Ulam's Game and Tree Code Give Error-Resistant Protocols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strategy in Ulam's Game and Tree Code Give Error-Resistant Protocols will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-398893