Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Coding Theory: The Capacity of Multidimensional Permutations With Restricted Movement
event speaker icon
Dor Elimelech (Ben-Gurion University)
event date icon
Sunday, 19.01.2020, 14:30
event location icon
Room 601 Taub Bld.
The study of permutations is motivated by their application in coding for flash memories, and their relevance in different applications of networking technologies and various channels. We study the multidimensional constrained systems of $\mathbb{Z}^d$-permutations with restricted movement. During the talk, we will show a correspondence between these restricted permutations and perfect matchings. We will 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 will prove that the capacity of $ \mathbb{Z} ^d$-permutations restricted by a set with full affine dimension depends only on the size of the set. We will use this result in order to compute the exact capacity for a class of two-dimensional constrained systems.