On communication complexity of bent functions from Maiorana–McFarland class
- 作者: Marchenko A.1
-
隶属关系:
- Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
- 期: 卷 37, 编号 6 (2016)
- 页面: 730-733
- 栏目: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/198427
- DOI: https://doi.org/10.1134/S1995080216060172
- ID: 198427
如何引用文章
详细
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.
作者简介
A. Marchenko
Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies
编辑信件的主要联系方式.
Email: Anton.Marchenko@kpfu.ru
俄罗斯联邦, Kremlevskaya ul. 35, Kazan, Tatrstan, 420008