Geometry of Translations on a Boolean Cube
- Autores: Vyalyi M.N.1,2,3, Leontiev V.K.1
-
Afiliações:
- Dorodnitsyn Computing Center of the Russian Academy of Sciences
- Moscow Institute of Physics and Technology (State University)
- National Research University-Higher School of Economics
- Edição: Volume 55, Nº 2 (2019)
- Páginas: 152-173
- Seção: Large Systems
- URL: https://journal-vniispk.ru/0032-9460/article/view/166595
- DOI: https://doi.org/10.1134/S0032946019020042
- ID: 166595
Citar
Resumo
The operation of Minkowski addition of geometric figures has a discrete analog, addition of subsets of a Boolean cube viewed as a vector space over the two-element field. Subsets of the Boolean cube (or multivariable Boolean functions) form a monoid with respect to this operation. This monoid is of interest in classical discrete analysis as well as in a number of problems related to information theory. We consider several complexity aspects of this monoid, namely structural, algorithmic, and algebraic.
Palavras-chave
Sobre autores
M. Vyalyi
Dorodnitsyn Computing Center of the Russian Academy of Sciences; Moscow Institute of Physics and Technology (State University); National Research University-Higher School of Economics
Autor responsável pela correspondência
Email: vyalyi@gmail.com
Rússia, Moscow; Moscow; Moscow
V. Leontiev
Dorodnitsyn Computing Center of the Russian Academy of Sciences
Autor responsável pela correspondência
Email: vkleontiev@yandex.ru
Rússia, Moscow
Arquivos suplementares
