Technical Program

Paper Detail

Paper IDA.4.4
Paper Title The Capacity of Multidimensional Permutations with Restricted Movement
Authors Dor Elimelech, Ben-Gurion University of the Negev, Israel
Session A.4: Combinatorial Coding Theory I
Presentation Lecture
Track Algebraic and Combinatorial Coding Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract We study the multidimensional constrained systems of $\Z^d$-permutations with restricted movement. We show a correspondence between these restricted permutations and perfect matchings. We use the theory of perfect matchings to investigate several two-dimensional cases, for which we compute the exact capacity of the constrained system, and prove the existence of a polynomial-time algorithm for counting admissible patterns. We prove that the capacity of $\Z^d$-permutations restricted by a set with full affine dimension depends only on the size of the set. We use this result in order to compute the exact capacity for a class of two-dimensional constrained systems.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!