Functions without short implicents. Part II: Construction

P. V. Roldugin ; A. V. Tarasov

Diskretnaya Matematika, Tome 27 (2015) no. 4, pp. 120-132

Résumé

This paper is a continuation of the paper ‘Functions without short implicents. Part I: lower estimates of weights’. In Part II we propose various methods of construction of $n$-place Boolean functions not admitting implicents of $k$ variables. The first of the methods proposed is based on the gradient algorithm, the second and the third ones depend on a certain combinatorial principle of construction, while the fourth method is based on a random choice of elements in the function support. The above methods have different efficiency depending on the value of $k$. We give upper estimates for the minimal value $w\left( {n,\;k} \right)$ of weights of the so-constructed functions. Together with the lower estimates of $w\left( {n,\;k} \right)$ from the first part of the paper this allows us to obtain an asymptotically sharp estimate $w\left( {n,\;k} \right) = \Theta \left( {\ln n} \right)$ as $n \to \infty$.

Détail

Keywords: Boolean functions, implicents, methods of construction of functions, weight of a Boolean function.