Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PERMUTATION CODES:
Reports tagged with permutation codes:
TR20-192 | 27th December 2020
Oded Goldreich, Avi Wigderson

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

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=N(n)=(n!)^{\Omega(1)}$ pairwise far apart permutations $\{\pi_i:[n]\to[n]\}_{i\in[N]}$ and ... more >>>

ISSN 1433-8092 | Imprint