Tests for multiple monotone symmetric conglutinations of variables in Boolean functions

A linear lower and a quadratic upper bound on the Shannon function for the length of a detecting test for multiple monotone symmetric conglutinations are proved. Additionally, the exact value of the Shannon function for the length of a diagnostic test for multiple monotone symmetric conglutinations is found. Some of the variables of a Boolean function are said to conglutinate if each of them is replaced by a function of these variables. A conglutination is called multiple if there are several groups of conglutinated variables.     

Length of diagnostic tests for Boolean circuits

Mathematical Notes -     

An algorithm for minimizing Boolean functions

The Cranfield method of minimizing Boolean functions is examined, and it is shown that the method does not always produce all the minimal sums. An algorithm is given which produces all the minimal sums and uses the Cranfield method as a first stage in the minimization procedure.     

Universal functions for classes of Boolean polynomials

The following problem is considered: Find Boolean function f of n variables with the property that, given any polynomial p of degree at most s, there exists a set of n-tuples such that p is the only polynomial of degree at most s taking the same values as f at these n-tuples. It is shown that for any fixed s and sufficiently large n, such a function exists and can be chosen from among those with domains of cardinality that grow as O(n ^s ).     

On estimates of Shannon functions of the length of unit tests for transpositions of variables

A nontrival upper estimate of the form n √2n (1 + o(1)) is proposed for the Shannon function of the length of the unit checking test for transpositions of variables of a Boolean function from P ₂ ⁿ , and it is proved that the Shannon function of the length of a unit diagnostic test for transpositions of variables of a Boolean function from P ₂ ⁿ has an asymptotics of the form n ²/2.     

On the suppression of variables in Boolean equations

The resultant of suppression of variables from a Boolean equation is a Boolean equation, derived from the parent equation, whose solutions are exactly those of the parent equation that do not involve the suppressed variables. Two examples in the literature are discussed, in which it is necessary to solve a Boolean equation while excluding solutions involving certain variables. In such cases it would be advantageous to solve the resultant of suppression of those variables rather than solving the original equation and filtering the desired solutions from the results.     

Influences of monotone Boolean functions

Recently, Keller and Pilpel conjectured that the influence of a monotone Boolean function does not decrease if we apply to it an invertible linear transformation. Our aim in this short note is to prove this conjecture.     

Compositional complexity of Boolean functions

We define two measures, γ and c, of complexity for Boolean functions. These measures are related to issues of functional decomposition which (for continuous functions) were studied by Arnol'd, Kolmogorov, Vitu?kin and others in connection with Hilbert's 13th Problem. This perspective was first applied to Boolean functions in [1]. Our complexity measures differ from those which were considered earlier [3, 5, 6, 9, 10] and which were used by Ehrenfeucht and others to demonstrate the great complexity of most decision procedures. In contrast to other measures, both γ and c (which range between 0 and 1) have a more combinatorial flavor and it is easy to show that both of them are close to 0 for literally all “meaningful” Boolean functions of many variables. It is not trivial to prove that there exist functions for which c is close to 1, and for γ the same question is still open. The same problem for all traditional measures of complexity is easily resolved by statistical considerations.     

Exclusion sensitivity of Boolean functions

Recently the study of noise sensitivity and noise stability of Boolean functions has received considerable attention. The purpose of this paper is to extend these notions in a natural way to a different class of perturbations, namely those arising from running the symmetric exclusion process for a short amount of time. In this study, the case of monotone Boolean functions will turn out to be of particular interest. We show that for this class of functions, ordinary noise sensitivity and noise sensitivity with respect to the complete graph exclusion process are equivalent. We also show this equivalence with respect to stability. After obtaining these fairly general results, we study “exclusion sensitivity” of critical percolation in more detail with respect to medium-range dynamics. The exclusion dynamics, due to its conservative nature, is in some sense more physical than the classical i.i.d. dynamics. Interestingly, we will see that in order to obtain a precise understanding of the exclusion sensitivity of percolation, we will need to describe how typical spectral sets of percolation diffuse under the underlying exclusion process.     

Dualization of regular Boolean functions

A monotonic Boolean function is regular if its variables are naturally ordered by decreasing ‘strength’, so that shifting to the right the non-zero entries of any binary false point always yields another false point. Peled and Simeone recently published a polynomial algorithm to generate the maximal false points (MFP's) of a regular function from a list of its minimal true points (MTP's). Another efficient algorithm for this problem is presented here, based on characterization of the MFP's of a regular function in terms of its MTP's. This result is also used to derive a new upper bound on the number of MFP's of a regular function.     

Interior and exterior functions of positive Boolean functions

The interior and exterior functions of a Boolean function f were introduced in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209–231), as stability (or robustness) measures of the f. In this paper, we investigate the complexity of two problems -INTERIOR and -EXTERIOR, introduced therein. We first answer the question about the complexity of -INTERIOR left open in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209–231); it has no polynomial total time algorithm even if is bounded by a constant, unless P=NP. However, for positive h-term DNF functions with h bounded by a constant, problems -INTERIOR and -EXTERIOR can be solved in (input) polynomial time and polynomial delay, respectively. Furthermore, for positive k-DNF functions, -INTERIOR for two cases in which k=1, and and k are both bounded by a constant, can be solved in polynomial delay and in polynomial time, respectively.     

Construction of balanced Boolean functions with high nonlinearity,good local and global avalanche characteristics

Boolean functions possessing multiple cryptographic criteria play an important role in the design of symmetric cryptosystems. The following criteria for cryptographic Boolean functions are often considered: high nonlinearity, balancedness, strict avalanche criterion, and global avalanche characteristics. The trade-off among these criteria is a difficult problem and has attracted many researchers. In this paper, two construction methods are provided to obtain balanced Boolean functions with high nonlinearity. Besides, the constructed functions satisfy strict avalanche criterion and have good global avalanche characteristics property. The algebraic immunity of the constructed functions is also considered.     

Centered forms for functions in several variables

R. E. Moore [3] has introduced the centered form of a rational function f for obtaining good and easily computable approximations which include the exact range of f over an interval X. Moore's definition is implicit, while explicit formulas for the centered form are given in [8] and [9]. In [9], centered forms of higher order for functions of one variable are developed which lead to better estimations than the centered forms defined originally. In this paper, centered forms of higher order for rational functions in several variables are explicitly defined. They also give better approximations than the centered forms defined originally.