2004/10/18 by Marcin Peczarski, Peczarski, Marcin
Computer Science · Mathematics · #Artificial Intelligence in Games #Distributed #FOS: Computer and information sciences #Information Theory (cs.IT) #Mobile Agent-Based Network Management #Parallel #Teaching and Learning Programming #and Cluster Computing (cs.DC) #cs.DC #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0410043
10 pages, 2 figures
arxiv created 2004/10/18 · openalex publication_date 2004/10/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.