An improvement on the complexity of factoring read-once Boolean functions

Read-once functions have gained recent, renewed interest in the fields of theory and algorithms of Boolean functions, computational learning theory and logic design and verification. In an earlier paper [M.C. Golumbic, A. Mintz, U. Rotics, Factoring and recognition of read-once functions using cographs and normality, and the readability of functions associated with partial k-trees, Discrete Appl. Math. 154 (2006) 1465-1677], we presented the first polynomial-time algorithm for recognizing and factoring read-once functions, based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrence graph is P₄-free.In this note, we improve the complexity bound by showing that the method can be modified slightly, with two crucial observations, to obtain an O(n|f|) implementation, where |f| denotes the length of the DNF expression of a positive Boolean function f, and n is the number of variables in f. The previously stated bound was O(n²k), where k is the number of prime implicants of the function. In both cases, f is assumed to be given as a DNF formula consisting entirely of the prime implicants of the function.     

Uniform approximation of continuous functions by probability functions of Boolean bases

Random Boolean expressions obtained by random and independent substitution of the constants 1, 0 with probabilities p, 1 ? p, respectively, into random non-iterated formulas over a given basis are considered. The limit of the probability of appearance of expressions with the value 1 under unrestricted growth of the complexity of expressions, which is called the probability function, is considered. It is shown that for an arbitrary continuous function f(p) mapping the segment [0, 1] into itself there exists a sequence of bases whose probability functions uniformly approximate the function f(p) on the segment [0, 1].     

On random orderings of variables for parity ordered binary decision diagrams

Ordered binary decision diagrams (OBDDs) are a model for representing Boolean functions. There is also a more powerful variant called parity OBDDs. The size of the representation of a given function depends in both these models on the chosen ordering of the variables. It is known that there are functions such that almost all orderings of their variables yield an OBDD of polynomial size, but there are also some exceptional orderings, for which the size is exponential. We prove that for parity OBDDs, the size for a random ordering and the size for the worst ordering are polynomially related. More exactly, for every ϵ>0 there is a number c>0 such that the following holds. If a Boolean function f of n variables is such that a random ordering of the variables yields a parity OBDD for f of size at most s with probability at least ϵ, where s≥n, then every ordering of the variables yields a parity OBDD for f of size at most s^c. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 233–239, 2000     

On extended algebraic immunity

Algebraic immunity (AI) measures the resistance of a Boolean function f against algebraic attack. Extended algebraic immunity (EAI) extends the concept of algebraic immunity, whose point is that a Boolean function f may be replaced by another Boolean function f ^c called the algebraic complement of f. In this paper, we study the relation between different properties (such as weight, nonlinearity, etc.) of Boolean function f and its algebraic complement f ^c . For example, the relation between annihilator sets of f and f ^c provides a faster way to find their annihilators than previous report. Next, we present a necessary condition for Boolean functions to be of the maximum possible extended algebraic immunity. We also analyze some Boolean functions with maximum possible algebraic immunity constructed by known existing construction methods for their extended algebraic immunity.     

Relations between threshold and <Emphasis Type="Italic">k</Emphasis>-interval Boolean functions

Every k-interval Boolean function f can be represented by at most k intervals of integers such that vector x is a truepoint of f if and only if the integer represented by x belongs to one of these k (disjoint) intervals. Since the correspondence of Boolean vectors and integers depends on the order of bits an interval representation is also specified with respect to an order of variables of the represented function. Interval representation can be useful as an efficient representation for special classes of Boolean functions which can be represented by a small number of intervals. In this paper we study inclusion relations between the classes of threshold and k-interval Boolean functions. We show that positive 2-interval functions constitute a (proper) subclass of positive threshold functions and that such inclusion does not hold for any k>2. We also prove that threshold functions do not constitute a subclass of k-interval functions, for any k.     

Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity

So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n²) time and O(n) space complexity. We use the term “Annihilator Immunity” instead of “Algebraic Immunity” referred in the recent papers [3–5, 9, 18, 19]. Please see Remark 1 for the details of this notational change     

An Analog Characterization of the Grzegorczyk Hierarchy

We study a restricted version of Shannon's general purpose analog computer in which we only allow the machine to solve linear differential equations. We show that if this computer is allowed to sense inequalities in a differentiable way, then it can compute exactly the elementary functions, the smallest known recursive class closed under time and space complexity. Furthermore, we show that if the machine has access to a function f(x) with a suitable growth as x goes to infinity, then it can compute functions on any given level of the Grzegorczyk hierarchy. More precisely, we show that the model contains exactly the nth level of the Grzegorczyk hierarchy if it is allowed to solve n−3 non-linear differential equations of a certain kind. Therefore, we claim that, at least in this region of the complexity hierarchy, there is a close connection between analog complexity classes, the dynamical systems that compute them, and classical sets of subrecursive functions.     

Exclusive and essential sets of implicates of Boolean functions

In this paper we study relationships between CNF representations of a given Boolean function f and certain sets of implicates of f. We introduce two definitions of sets of implicates which are both based on the properties of resolution. The first type of sets, called exclusive sets of implicates, is shown to have a functional property useful for decompositions. The second type of sets, called essential sets of implicates, is proved to possess an orthogonality property, which implies that every CNF representation and every essential set must intersect. The latter property then leads to an interesting question, to which we give an affirmative answer for some special subclasses of Horn Boolean functions.     

On the security of the Feng–Liao–Yang Boolean functions with optimal algebraic immunity against fast algebraic attacks

In the past few years, algebraic attacks against stream ciphers with linear feedback function have been significantly improved. As a response to the new attacks, the notion of algebraic immunity of a Boolean function f was introduced, defined as the minimum degree of the annihilators of f and f + 1. An annihilator of f is a nonzero Boolean function g, such that fg = 0. There is an increasing interest in construction of Boolean functions that possess optimal algebraic immunity, combined with other characteristics, like balancedness, high nonlinearity, and high algebraic degree. In this paper, we investigate a recently proposed infinite class of balanced Boolean functions with optimal algebraic immunity, optimum algebraic degree and much better nonlinearity than all the previously introduced classes of Boolean functions with maximal algebraic immunity. More precisely, we study the resistance of the functions against one of the new algebraic attacks, namely the fast algebraic attacks (FAAs). Using the special characteristics of the family members, we introduce an efficient method for the evaluation of their behavior against these attacks. The new algorithm is based on the well studied Berlekamp–Massey algorithm.     

On Some Special Classes of Sequential Dynamical Systems

Sequential Dynamical Systems (SDSs) are mathematical models for analyzing simulation systems. We investigate phase space properties of some special classes of SDSs obtained by restricting the local transition functions used at the nodes. We show that any SDS over the Boolean domain with symmetric Boolean local transition functions can be efficiently simulated by another SDS which uses only simple threshold and simple inverted threshold functions, where the same threshold value is used at each node and the underlying graph is d-regular for some integer d. We establish tight or nearly tight upper and lower bounds on the number of steps needed for SDSs over the Boolean domain with 1-, 2- or 3-threshold functions at each of the nodes to reach a fixed point. When the domain is a unitary semiring and each node computes a linear combination of its inputs, we present a polynomial time algorithm to determine whether such an SDS reaches a fixed point. We also show (through an explicit construction) that there are Boolean SDSs with the NOR function at each node such that their phase spaces contain directed cycles whose length is exponential in the number of nodes of the underlying graph of the SDS.AMS Subject Classification: 68Q10, 68Q17, 68Q80.     

The Rivest–Vuillemin Conjecture on Monotone Boolean Functions Is True for Ten Variables

A Boolean function f(x₁, …, x_n) is elusive if every decision tree evaluating f must examine all n variables in the worst case. Rivest and Vuillemin conjectured that every nontrivial monotone weakly symmetric Boolean function is elusive. In this note, we show that this conjecture is true for n=10.     

Testing Monotonicity

at arguments of its choice, the test always accepts a monotone f, and rejects f with high probability if it is ε-far from being monotone (i.e., every monotone function differs from f on more than an ε fraction of the domain). The complexity of the test is O(n/ε). The analysis of our algorithm relates two natural combinatorial quantities that can be measured with respect to a Boolean function; one being global to the function and the other being local to it. A key ingredient is the use of a switching (or sorting) operator on functions. Received March 29, 1999     

Lower estimates of circuit complexity in the basis of antichain functions

The antichain function is a characteristic function of an antichain in the Boolean cube. The set of antichain functions is an infinite complete basis. We study the computational complexity of Boolean functions over an antichain functional basis. In this paper we prove an asymptotic lower bound of order $\sqrt n $ for the computational complexity of a linear function, a majority function, and almost all Boolean functions of n variables.     

Games played by Boole and Galois

We define an infinite class of 2-pile subtraction games, where the amount that can be subtracted from both piles simultaneously is an extended Boolean function f of the size of the piles, or a function over GF(2). Wythoff's game is a special case. For each game, the second player winning positions are a pair of complementary sequences. Sample games are presented, strategy complexity questions are discussed, and possible further studies are indicated. The motivation stems from the major contributions of Professor Peter Hammer to the theory and applications of Boolean functions.     

Finitely additive,modular, and probability functions on pre-Semirings

In this paper, we define finitely additive, probability and modular functions over semiring-like structures. We investigate finitely additive functions with the help of complemented elements of a semiring. We also generalize some classical results in probability theory such as the law of total probability, Bayes’ theorem, the equality of parallel systems, and Poincaré’s inclusion-exclusion theorem. While we prove that modular functions over a couple of known semirings are almost constant, we show it is possible to define many different modular functions over some semirings such as bottleneck algebras and the semiring (Id(D),+,?), where D is a Dedekind domain.     

Recognizing the nonrepeating property in an arbitrary basis

Two classical problems are considered: recognizing the properties of a Boolean function given a column of its values and constructing a diagnostic test. The problems are investigated for nonrepeating functions in an arbitrary basis B. For the first problem, the decomposition method is applied to prove linear complexity of the corresponding sequential circuits; for the second problem we derive the order of the Shannon functions for a number of bases, in particular, for the basis of all functions of four variables. __________ Translated from Prikladnaya Matematika i Informatika, No. 23, pp. 67–84, 2006.     

And/or trees: A local limit point of view

We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say , and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees , the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees).     

Boolean functions with a simple certificate for CNF complexity

In this paper we study relationships between CNF representations of a given Boolean function $f$ and essential sets of implicates of $f$. It is known that every CNF representation and every essential set must intersect. Therefore the maximum number of pairwise disjoint essential sets of $f$ provides a lower bound on the size of any CNF representation of $f$. We are interested in functions, for which this lower bound is tight, and call such functions coverable. We prove that for every coverable function there exists a polynomially verifiable certificate (witness) for its minimum CNF size. On the other hand, we show that not all functions are coverable, and construct examples of non-coverable functions. Moreover, we prove that computing the lower bound, i.e. the maximum number of pairwise disjoint essential sets, is $NP$-hard under various restrictions on the function and on its input representation.     

Approximating Boolean functions by OBDDs

In learning theory and genetic programming, OBDDs are used to represent approximations of Boolean functions. This motivates the investigation of the OBDD complexity of approximating Boolean functions with respect to given distributions on the inputs. We present a new type of reduction for one-round communication problems that is suitable for approximations. Using this new type of reduction, we improve a known lower bound on the size of OBDD approximations of the hidden weighted bit function for uniformly distributed inputs to an asymptotically tight bound and prove new results about OBDD approximations of integer multiplication and squaring for uniformly distributed inputs.     

A definition of subjective possibility

Based on the setting of exchangeable bets, this paper proposes a subjectivist view of numerical possibility theory. It relies on the assumption that when an agent constructs a probability measure by assigning prices to lotteries, this probability measure is actually induced by a belief function representing the agent’s actual state of knowledge. We also assume that the probability measure proposed by the agent in the course of the elicitation procedure is constructed via the so-called pignistic transformation (mathematically equivalent to the Shapley value in game theory). We pose and solve the problem of finding the least informative belief function having a given pignistic probability. We prove that it is unique and consonant, thus induced by a possibility distribution. This result exploits a simple informational ordering, in agreement with partial orderings between belief functions, comparing their information content. The obtained possibility distribution is subjective in the same sense as in the subjectivist school in probability theory. However, we claim that it is the least biased representation of the agent’s state of knowledge compatible with the observed betting behaviour.