Separation results for Boolean function classes (Q2119852): Difference between revisions

The set of bits can be represented either as \(Q = \{0,1\}\) or \(Q = \{-1,+1\}\), and for each \(n\in\mathbb{Z}^+\) the space \(Q^n\) is endowed naturally of the structure of an \(n\)-dimensional \(\mathbb{Z}_2\)-vector space. Boolean maps are of the form \(Q^n\to Q\). Several classes of Boolean maps have been extensively studied. In Cryptography there are of great interest the bent functions, plateaued functions, functions satisfying the strict avalanche criterion, and functions satisfying propagation characteristics. In combinatorics and complexity theory the monotone functions, bounded-depth circuits and linear threshold functions have been analysed. For a given class \(C\) of Boolean maps, \(C_n\) denotes the subset of \(C\) consisting of the maps with domain \(Q^n\). Two classes \(C_0\) and \(C_1\) are {\em \(n_0\)-disjoint} if \(C_{0n}\cap C_{1n} = \emptyset\) for any \(n\geq n_0\). In order to prove \(n_0\)-disjointness of two classes \(C_0\) and \(C_1\), the authors propose to use a functional \(F:\{\mbox{Boolean maps}\}\to \mathbb{R}\) such that for any \(n\geq n_0\) if \(f_0\in C_{0n}\) and \(f_1\in C_{1n}\) then \(F(f_0)<F(f_1)\), because this condition entails obviously that \(C_0\) and \(C_1\) are \(n_0\)-disjoint. The proposed functional is a notion of influence of components, calculated in terms of Fourier transforms of Boolean maps. First, the class consisting of the bent maps, the maps satisfying the strict avalanche criterion, and the maps satisfying propagation characteristics is considered. Some sufficient conditions on \(n_0\) are stated for \(n_0\)-disjointness with each of the classes of monotone maps, linear threshold maps and maps computable with constant depth circuits. Later the class consisting of t\(k\)-plateaud maps is considered and some sufficient conditions on \(n_0\) are stated for \(n_0\)-disjointness with each of the classes of monotone maps, linear threshold maps and maps computable with constant depth circuits. For sure it is an interesting and effective novel approach to prove separation of Boolean maps classes.