Improved boolean formulas for the Ramsey graphs

In the theory of the random graphs, there are properties of graphs such that almost all graphs satisfy the property, but there is no effective way to find examples of such graphs. By the well-known results of Razborov, for some of these properties, e.g., some Ramsey property, there are Boolean formulas in ACC representing the graphs satisfying the property and having exponential number of vertices with respect to the number of variables of the formula. Razborov's proof is based on a probabilistic distribution on formulas of n variables of size approximately nd² log d, where d is a polynomial in n, and depth 3 in the basis { ∧, ⊕} with the following property: The restriction of the formula randomly chosen from the distribution to any subset A of the Boolean cube {0, 1}ⁿ of size at most d has almost uniform distribution on the functions A → {0, 1}. We show a modified probabilistic distribution on Boolean formulas which is defined on formulas of size at most nd log² d and has the same property of the restrictions to sets of size at most d as the original one. This allows us to obtain formulas the complexity of which is a polynomial of a smaller degree in n than in Razborov's paper while the represented graphs satisfy the same properties.     

Upper bounds on the depth of symmetric Boolean functions

A new method for implementing the counting function with Boolean circuits is proposed. It is based on modular arithmetic and allows us to derive new upper bounds for the depth of the majority function of n variables: 3.34log₂ n over the basis B ₂ of all binary Boolean functions and 4.87log₂ n over the standard basis B ₀ = {∧, ∨, ?}. As a consequence, the depth of the multiplication of n-digit binary numbers does not exceed 4.34log₂ n and 5.87log₂ n over the bases B ₂ and B ₀, respectively. The depth of implementation of an arbitrary symmetric Boolean function of n variables is shown to obey the bounds 3.34log₂ n and 4.88log₂ n over the same bases.     

Construction of noniterated boolean functions in the basis {&;, ∨, −} and estimation of their number

In this paper we consider noniterated Boolean functions in the basis {&;, ∨, ?}. We obtain the canonical form of the formula for a noniterated function in this basis. We construct the set of such formulas with respect to variables x ₁, …, x _n and calculate the number of its elements. Based on these results, we obtain the upper and lower bounds for the number of noniterated Boolean functions of n variables in the basis under consideration.     

On the symmetric properties of APN functions

We study the symmetric properties of APN functions as well as the structure and properties of the range of an arbitrary APN function. We prove that there is no permutation of variables that preserves the values of an APN function. Upper bounds for the number of symmetric coordinate Boolean functions in an APN function and its coordinate functions invariant under a cyclic shift are obtained. For n ≤ 6, some upper bounds for the maximal number of identical values of an APN function are given and a lower bound is found for different values of an arbitrary APN function of n variables.     

Intrinsic ordering,combinatorial numbers and reliability engineering

A new algorithm for evaluating the top event probability of large fault trees (FTs) is presented. This algorithm does not require any previous qualitative analysis of the FT. Indeed, its efficiency is independent of the FT logic, and it only depends on the number n of basic system components and on their failure probabilities. Our method provides exact lower and upper bounds on the top event probability by using new properties of the intrinsic order relation between binary strings. The intrinsic order enables one to select binary n  -tuples with large occurrence probabilities without necessity to evaluate them. This drastically reduces the complexity of the problem from exponential (2ⁿ$2^n$ binary n-tuples) to linear (n Boolean variables). Our algorithm is mainly based on a recursive formula for rapidly computing the sum of the occurrence probabilities of all binary n-tuples with weight m whose 1s are placed among the k right-most positions. This formula, as well as the balance between accuracy and computational cost, is closely related to the famous Pascal’s triangle.     

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.     

Satisfiability of mixed Horn formulas

In this paper the class of mixed Horn formulas is introduced that contain a Horn part and a 2-CNF (conjunctive normal form) (also called quadratic) part. We show that SAT remains NP-complete for such instances and also that any CNF formula can be encoded in terms of a mixed Horn formula in polynomial time. Further, we provide an exact deterministic algorithm showing that SAT for mixed Horn formulas containing n variables is solvable in time O(2^0.5284n). A strong argument showing that it is hard to improve a time bound of O(2^n/2) for mixed Horn formulas is provided. We also obtain a fixed-parameter tractability classification for SAT restricted to mixed Horn formulas C of at most k variables in its positive 2-CNF part providing the bound O(∥C∥2^0.5284k). We further show that the NP-hard optimization problem minimum weight SAT for mixed Horn formulas can be solved in time O(2^0.5284n) if non-negative weights are assigned to the variables. Motivating examples for mixed Horn formulas are level graph formulas [B. Randerath, E. Speckenmeyer, E. Boros, P. Hammer, A. Kogan, K. Makino, B. Simeone, O. Cepek, A satisfiability formulation of problems on level graphs, ENDM 9 (2001)] and graph colorability formulas.     

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₀.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

Linear equations and interpolation in Boolean algebra

The authors generalize the classical interpolation formula for Boolean functions of n variables. A characterization of all interpolating systems with 2ⁿ elements is obtained. The methods of proof used are intimately related to the solution of linear Boolean equations.     

Synthesis of formulas whose complexity and depth do not exceed the asymptotically best estimates of high degree of accuracy

We study problems concerning optimal realizations of arbitrary Boolean functions by formulas in the standard basis {&;, V, ¬} in the presence of two optimality criteria: the depth and the complexity. Both the complexity and depth of Boolean functions are investigated from the point of view of so-called asymptotically best estimates of high degree of accuracy for the corresponding Shannon functions. Such estimates produce an asymptotics not only for the Shannon function, but also for the first remainder term of its standard asymptotic expansion. For any Boolean function depending on n variables, we prove that it is possible to construct a realizing formula in the basis {&;, V, ¬} so that its depth and complexity do not exceed values of the corresponding Shannon functions for the argument equal to n in the sense of asymptotic estimates of high degree of accuracy.     

Density condensation of Boolean formulas

The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is “easier” than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2ⁿ, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms.     

On the complexity of a cyclic shift of a set of real numbers

The complexity of implementing a cyclic shift of a 2ⁿ-tuple of real numbers by Boolean circuits over the basis consisting of a ternary choice function and all binary Boolean functions is shown to be 2ⁿ n.     

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 ).     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.     

Formulas for approximating pseudo-Boolean random variables

We consider {0,1}ⁿ as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. We then derive explicit formulas for approximating a pseudo-Boolean random variable by a linear function if the measure is permutation-invariant, and by a function of degree at most k if the measure is a product measure. These formulas generalize results due to Hammer-Holzman and Grabisch-Marichal-Roubens. We also derive a formula for the best faithful linear approximation that extends a result due to Charnes-Golany-Keane-Rousseau concerning generalized Shapley values. We show that a theorem of Hammer-Holzman that states that a pseudo-Boolean function and its best approximation of degree at most k have the same derivatives up to order k does not generalize to this setting for arbitrary probability measures, but does generalize if the probability measure is a product measure.     

Constructing Ramsey graphs from Boolean function representations

Explicit construction of Ramsey graphs or graphs with no large clique or independent set, has remained a challenging open problem for a long time. While Erdös’ probabilistic argument shows the existence of graphs on 2n vertices with no clique or independent set of size 2 ⁿ , the best explicit constructions achieve a far weaker bound. There is a connection between Ramsey graph constructions and polynomial representations of Boolean functions due to Grolmusz; a low degree representation for the OR function can be used to explicitly construct Ramsey graphs [17,18]. We generalize the above relation by proposing a new framework. We propose a new definition of OR representations: a pair of polynomials represent the OR function if the union of their zero sets contains all points in {0, 1} ⁿ except the origin. We give a simple construction of a Ramsey graph using such polynomials. Furthermore, we show that all the known algebraic constructions, ones to due to Frankl-Wilson [12], Grolmusz [18] and Alon [2] are captured by this framework; they can all be derived from various OR representations of degree O(√n) based on symmetric polynomials. Thus the barrier to better Ramsey constructions through such algebraic methods appears to be the construction of lower degree representations. Using new algebraic techniques, we show that better bounds cannot be obtained using symmetric polynomials.     

Rotation symmetric Boolean functions—Count and cryptographic properties

Rotation symmetric (RotS) Boolean functions have been used as components of different cryptosystems. This class of Boolean functions are invariant under circular translation of indices. Using Burnside's lemma it can be seen that the number of n-variable rotation symmetric Boolean functions is 2^g_n, where g_n=(1/n)∑_t|nφ(t)2^n/t, and φ(.) is the Euler phi-function. In this paper, we find the number of short and long cycles of elements in having fixed weight, under the RotS action. As a consequence we obtain the number of homogeneous RotS functions having algebraic degree w. Our results make the search space of RotS functions much reduced and we successfully analyzed important cryptographic properties of such functions by executing computer programs. We study RotS bent functions up to 10 variables and observe (experimentally) that there is no homogeneous rotation symmetric bent function having degree >2. Further, we studied the RotS functions on 5,6,7 variables by computer search for correlation immunity and propagation characteristics and found some functions with very good cryptographic properties which were not known earlier.     

A study on monotone self-dual Boolean functions

This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form (IDNF) do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O(n³).