In this work we consider the communication of information in the presence of synchronization errors. Specifically, we consider permutation channels in which a transmitted word x=(x_1,\ldots,x_n) is corrupted by a permutation \pi\in S_n (the set of all permutations on n elements) to yield the received word y=(y_1,\ldots,y_n) where y_i=x_{\pi(i)}.

We initiate the study of worst-case (or zero-error) communication over permutation channels that distort the information by applying permutations \pi which are limited to displacing any symbol by at most r locations, i.e. permutations \pi with weight at most r in the \ell_\infty-metric. We present direct and recursive constructions, as well as bounds on the rate of such channels for binary and general alphabets. Specific attention is given to the case of r=1. A list of interesting open problems in this area will be given.

Joint work with Michael Langberg and Moshe Schwartz.