Stagger Edit-Distance Tree Codes for Interactive Communication

MARCUS M. PENATE and CHRISTOPHER T. PHAM

Error-correcting codes allow for reliable transmission and storage of information. In communications, these codes are traditionally implemented in a one-way setting where each received message is immediately decoded; however, advances in distributed computing has motivated the need for an interactive communication setting where many short messages (called a conversation) are alternately sent between two parties through an adversarially noisy channel before decoding is performed. Such conversations can be protected against insertion/deletion errors by encoding them using Edit-Distance Tree Codes (EDTCs), where messages are represented by edges along a tree path. However, no explicit deterministic constructions of EDTCs are known to date (although such codes have been proven to exist). We describe a stagger tree code construction for binary and quaternary conversations that yields EDTCs with good parameters and performs better on average than other natural and/or greedy approaches.