2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | A.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
