## Constructing Large Families of Pairwise Far Permutations:
Good Permutation Codes Based on the Shuffle-Exchange Network

#### Webpage for a paper by Oded Goldreich and Avi Wigderson

#### Abstract

We consider the problem of efficiently constructing an as large as possible
family of permutations such that each pair of permutations are far part
(i.e., disagree on a constant fraction of their inputs).
Specifically, for every $n\in\N$, we present a collection of
$N=3DN(n)=3D(n!)^{\Omega(1)}$ pairwise far apart permutations
$\{\pi_i:[n]\to[n]\}_{i\in[N]}$ and a polynomial-time algorithm that on
input $i\in[N]$ outputs an explicit description of $\pi_i$.

From a coding theoretic perspective, we construct permutation codes of
constant relative distance and constant rate along with efficient encoding
(and decoding) algorithms.
This construction is easily extended to produce codes on smaller alphabets
in which every codeword is balanced; namely, each symbol appears the same
number of times.

Our construction combines routing on the Shuffle-Exchange network with any
good binary error correcting code.
Specifically, we uses codewords of a good binary code in order to determine
the switching instructions in the Shuffle-Exchange network.

#### Material available on-line

- First version posted:
Dec 2020.
- Revisions: none yet.

**Additioanl grant acknowledgement**:
This project has received funding from the European Research Council (ERC)
under the European Union's Horizon 2020 research and innovation programme
(grant agreement No. 819702).

Back to
either Oded Goldreich's homepage
or general list of papers.