Email this article On communication complexity of bent functions from Maiorana–McFarland class
- Authors: Marchenko A.1
-
Affiliations:
- Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
- Issue: Vol 37, No 6 (2016)
- Pages: 730-733
- Section: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/198427
- DOI: https://doi.org/10.1134/S1995080216060172
- ID: 198427
Cite item
Open Access
Access granted
Subscription Access
Abstract
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.
About the authors
A. Marchenko
Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
Author for correspondence.
Email: Anton.Marchenko@kpfu.ru
Russian Federation, Kremlevskaya ul. 35, Kazan, Tatrstan, 420008
