A new class of bent and hyper-bent Boolean functions in polynomial forms

Bent functions are maximally nonlinear Boolean functions and exist only for functions with even number of inputs. This paper is a contribution to the construction of bent functions over ${\mathbb{F}_{2^{n}}}$ (n = 2m) having the form ${f(x) = tr_{o(s_1)} (a x^ {s_1}) + tr_{o(s_2)} (b x^{s_2})}$ where o(s _i ) denotes the cardinality of the cyclotomic class of 2 modulo 2 ⁿ ? 1 which contains s _i and whose coefficients a and b are, respectively in ${F_{2^{o(s_1)}}}$ and ${F_{2^{o(s_2)}}}$ . Many constructions of monomial bent functions are presented in the literature but very few are known even in the binomial case. We prove that the exponents s ₁ = 2 ^m ? 1 and ${s_2={\frac {2^n-1}3}}$ , where ${a\in\mathbb{F}_{2^{n}}}$ (a ?? 0) and ${b\in\mathbb{F}_{4}}$ provide a construction of bent functions over ${\mathbb{F}_{2^{n}}}$ with optimum algebraic degree. For m odd, we give an explicit characterization of the bentness of these functions, in terms of the Kloosterman sums. We generalize the result for functions whose exponent s ₁ is of the form r(2 ^m ? 1) where r is co-prime with 2 ^m  + 1. The corresponding bent functions are also hyper-bent. For m even, we give a necessary condition of bentness in terms of these Kloosterman sums.     

Complexity of function systems over a finite field in the class of polarized polynomial forms

The Shannon complexity of a function system over a q-element finite field which contains m functions of n variables in the class of polarized polynomial forms is exactly evaluated: L _q ^PPF (n,m) = q ⁿ for all n ≥ 1, m ≥ 2, and all possible odd q. It has previously been known that L₂^PPF (n,m) = 2 ⁿ and L₃^PPF (n,m) = 3 ⁿ for all n ≥ 1 and m ≥ 2.     

A polynomial decomposition of Boolean functions

Translated from Matematicheskie Zametki, Vol. 53, No. 2, pp. 25–29, February, 1993.     

Binary terms in polynomial representations of Boolean functions

Polynomial representations of Boolean functions by binary terms are considered. The construction of terms involves variables and residual functions. Special cases of such representations are the decomposition of a function with respect to variables, Zhegalkin polynomials, and representations of functions as sums of conjunctions of residual functions.     

Complexity of implementation of Boolean functions by real formulas

Upper complexity estimates are proved for implementation of Boolean functions by formulas in bases consisting of a finite number of continuous real functions and a continuum of constants. For some bases upper complexity estimates coincide with lower ones.     

Complexity and depth of formulas for symmetric Boolean functions

A new approach for implementation of the counting function for a Boolean set is proposed. The approach is based on approximate calculation of sums. Using this approach, new upper bounds for the size and depth of symmetric functions over the basis B₂ of all dyadic functions and over the standard basis B₀ = {∧, ∨,^- } were non-constructively obtained. In particular, the depth of multiplication of n-bit binary numbers is asymptotically estimated from above by 4.02 log₂n relative to the basis B₂ and by 5.14log₂n relative to the basis B₀.     

Boolean function minimization in the class of disjunctive normal forms

The survey focuses on minimization of boolean functions in the class of disjunctive normal forms (d.n.f.s) and covers the publications from 1953 to 1986. The main emphasis is on the mathematical direction of research in boolean function minimization: bounds of parameters of boolean functions and algorithmic difficulties of minimal d.n.f. synthesis). The survey also presents a classification of minimization algorithms and gives some examples of minimization heuristics with their efficiency bounds.Translated from Itogi Nauki i Tekhniki, Seriya Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 25, pp. 68–116, 1987.     

Complexity of sequential computations of partial Boolean functions by circuits

A pair (f, g) of partial Boolean functions is characterized by a tuple of parameters l _αβ that is the number of tuples $ \tilde x A pair (f, g) of partial Boolean functions is characterized by a tuple of parameters l _αβ that is the number of tuples such that (f( ), g( )) = (α, β), where α and β take the values 0, 1, and an undefined value. The sequential computation of (f, g) is considered when a circuit S _f for f is constructed first, and, next, it is completed by the construction up to a circuit S _f,g . It is shown that if the domain D(f) includes D(g) then it is possible to compute sequentially f and g in such a way that S _f and S _f,g are asymptotically minimal simultaneously (i.e., they satisfy the asymptotically best bounds on the complexity for corresponding classes); and, in general, these functions cannot be sequentially computed in the order g, f so that S _g and S _f,g are asymptotically minimal. An attainable lower bound is obtained on the size of the circuit S _f,g for the sequential computation. The information properties of partially defined data play an essential role whose study in the previous papers of the author is continued here. Original Russian Text ? L.A. Sholomov, 2007, published in Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 2007, Vol. 14, No. 1, pp. 110–139.     

Complexity of self-correcting circuits for some sequence of Boolean functions

k-Self-correcting circuits of functional elements in the basis {x ₁&x ₂, $ \bar x $ \bar x } are considered. It is assumed that constant faults on outputs of functional elements are of the same type. Inverters are supposed to be reliable in service. The weight of each inverter is equal to 1. Conjunctors can be reliable in service, or not reliable. Each reliable conjunctor implements a conjunction of two variables and has a weight p > k + 2. Each unreliable conjunctor implements a conjunction in its correct state and implements a Boolean constant δ (δ ∈ {0, 1}) otherwise. Each unreliable conjunctor has the weight 1. It is stated that the complexity of realization of monotone threshold symmetric functions $ f_2^n \left( {x_1 ,...,x_n } \right) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_1 x_j ,n = 3,4 $ f_2^n \left( {x_1 ,...,x_n } \right) = \mathop \vee \limits_{1 \leqslant i < j \leqslant n} x_1 x_j ,n = 3,4 , ... by such circuits asymptotically equals (k + 3)n.     

Composition of Post classes and normal forms of Boolean functions

The class composition C°K of Boolean clones, being the set of composite functions f(g₁,…,g_n) with f∈C, g₁,…,g_n∈K, is investigated. This composition C°K is either the join C∨K in the Post Lattice or it is not a clone, and all pairs of clones C,K are classified accordingly.Factorizations of the clone Ω of all Boolean functions as a composition of minimal clones are described and seen to correspond to normal form representations of Boolean functions. The median normal form, arising from the factorization of Ω with the clone SM of self-dual monotone functions as the leftmost composition factor, is compared in terms of complexity with the well-known DNF, CNF, and Zhegalkin (Reed-Muller) polynomial representations, and it is shown to provide a more efficient normal form representation.     

On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

Representations of Boolean functions by exclusive-OR sums (modulo 2) of pseudoproducts is studied. An ExOR-sum of pseudoproducts (ESPP) is the sum modulo 2 of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this form, and the length of a Boolean function in the class of ESPPs is defined as the minimum length of an ESPP representing this function. The Shannon function L ^ESPP(n) of the length of Boolean functions in the class of ESPPs is considered, which equals the maximum length of a Boolean function of n variables in this class. Lower and upper bounds for the Shannon function L ^ESPP(n) are found. The upper bound is proved by using an algorithm which can be applied to construct representations by ExOR-sums of pseudoproducts for particular Boolean functions.     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

On the Complexity of Minimizing Quasicyclic Boolean Functions

We investigate the Boolean functions that combine various properties: the extremal values of complexity characteristics ofminimization, the inapplicability of local methods for reducing the complexity of the exhaustion, and the impossibility to efficiently use sufficient minimality conditions. Some quasicyclic functions are constructed that possess the properties of cyclic and zone functions, the dominance of vertex sets, and the validity of sufficient minimality conditions based on independent families of sets. For such functions, we obtain the exponential lower bounds for the extent and special sets and also a twice exponential lower bound for the number of shortest and minimal complexes of faces with distinct sets of proper vertices.     

On a new class of functional equations satisfied by polynomial functions

Aequationes mathematicae - The classical result of L. Székelyhidi states that (under some assumptions) every solution of a general linear equation must be a polynomial function. It is known...