The Taub Faculty of Computer Science Events and Talks

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.