On communication complexity of bent functions from Maiorana–McFarland class
- Autores: Marchenko A.1
-
Afiliações:
- Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
- Edição: Volume 37, Nº 6 (2016)
- Páginas: 730-733
- Seção: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/198427
- DOI: https://doi.org/10.1134/S1995080216060172
- ID: 198427
Citar
Resumo
In this article we study two party Communication Complexity of Boolean bent functions from Maiorana–McFarland class. In particular, we describe connections between Maiorana–McFarland construction of bent functions and operations on matrix form of Boolean functions and show that bent functions of 2n variables from Maiorana–McFarland class have deterministic communication complexity equal n + 1. Finally, we show that not all bent functions have high communication complexity lower bound by giving the example of such function.
Sobre autores
A. Marchenko
Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
Autor responsável pela correspondência
Email: Anton.Marchenko@kpfu.ru
Rússia, Kremlevskaya ul. 35, Kazan, Tatrstan, 420008