On the boolean partial derivatives and their composition

The main goal of this work is to introduce the relation between the partial boolean derivatives of an n-variable boolean function and their directional boolean derivatives.     

Using a similarity measure for credible classification

This paper concerns classification by Boolean functions. We investigate the classification accuracy obtained by standard classification techniques on unseen points (elements of the domain, {0,1}ⁿ, for some n) that are similar, in particular senses, to the points that have been observed as training observations. Explicitly, we use a new measure of how similar a point x∈{0,1}ⁿ is to a set of such points to restrict the domain of points on which we offer a classification. For points sufficiently dissimilar, no classification is given. We report on experimental results which indicate that the classification accuracies obtained on the resulting restricted domains are better than those obtained without restriction. These experiments involve a number of standard data-sets and classification techniques. We also compare the classification accuracies with those obtained by restricting the domain on which classification is given by using the Hamming distance.     

Some Properties of Bent Functions

First, this paper discusses and sums up some properties of a pair of functions p（x）, q（x） that makes （y ＋ 1）p（x） ＋ yq（x） into a bent function. Then it discusses the properties of bent functions. Also, the upper and lower bounds of the number of bent functions on GF（2）2k are discussed.     

On the probability of union in the n-space

In this paper, our sets are orthants in $R^n$ and $N$, the number of them, is large ($N>n$). We introduce the modified inclusion–exclusion formula in order to efficiently calculate the probability of a union of such events. The new formula works in the bivariate case, and can also be used in $R^n,n\ge 3$ with a condition on the projected sets onto lower dimensional spaces. Numerical examples are presented.     

An Upper Bound on the Number of Iterations for Transforming a Boolean Function of Degree Greater or Equal Than 4 to a Function of Degree 3

The difficulty involved in characterizing the weight distribution of all Boolean functions of degree 3 is well-known [2, p. 446]. In [1] the author introduces a transformation on Boolean functions which changes their weights in a way that is easy to follow, and which, when iterated, reduces the degree of the function to 2 or 3. He concludes that it is just as difficult to characterize the weight of any function of degree 3 as it is for any other degree. The application of this transformation on a Boolean function defined on , increases the number of its variables by two. On the other hand, in order to reduce the degree of a function to 2 or 3 it is necessary to apply the tranformation a number of times that grows exponentially with respect to m. In this paper, a factorization method on Boolean functions that allows the establishment of an upper bound for the number of applications of the transformation is presented. It shows that, in general, it is possible to significantly decrease the number of iterations in this process of degree reduction.     

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.     

A Boolean measure of similarity

We propose a way of measuring the similarity of a Boolean vector to a given set of Boolean vectors, motivated in part by certain data mining or machine learning problems. We relate the similarity measure to one based on Hamming distance and we develop from this some ways of quantifying the ‘quality’ of a dataset.     

Juntas in the ℓ1‐grid and Lipschitz maps between discrete tori

We show that if , then is ‐close to a junta depending upon at most coordinates, where denotes the edge‐boundary of in the ‐grid. This bound is sharp up to the value of the absolute constant in the exponent. This result can be seen as a generalisation of the Junta theorem for the discrete cube, from [6], or as a characterisation of large subsets of the ‐grid whose edge‐boundary is small. We use it to prove a result on the structure of Lipschitz functions between two discrete tori; this can be seen as a discrete, quantitative analogue of a recent result of Austin [1]. We also prove a refined version of our junta theorem, which is sharp in a wider range of cases. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 253–279, 2016     

Decompositions of positive self-dual boolean functions

A coterie, which is used to realize mutual exclusion in distributed systems, is a family C of subsets such that any pair of subsets in C has at least one element in common, and such that no subset in C contains any other subset in C. Associate with a family of subsets C a positive Boolean function f_c such that f_c(x) = 1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f_c is dual-minor, and is a non-dominated (ND) coterie if and only if f_c is self-dual. We study in this paper the decomposition of a positive self-dual function into smaller positive self-dual functions, as it explains how to represent and how to construct the corresponding ND coterie. A key step is how to decompose a positive dual-minor function f into a conjunction of positive self-dual functions f₁,f₂,…, f_k. In addition to the general condition for this decomposition, we clarify the condition for the decomposition into two functions f₁, and f₂, and introduce the concept of canonical decomposition. Then we present an algorithm that determines a minimal canonical decomposition, and a very simple algorithm that usually gives a decomposition close to minimal. The decomposition of a general self-dual function is also discussed.     

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.     

Special subalgebras of Boolean algebras

We consider eight special kinds of subalgebras of Boolean algebras. In Section 1 we describe the relationships between these subalgebra notions. In succeeding sections we consider how the subalgebra notions behave with respect to the most common cardinal functions on Boolean algebras (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

On the complexity of constrained VC-classes

Sauer's lemma is extended to classes H_N of binary-valued functions h on [n]={1,…,n} which have a margin less than or equal to N on all x∈[n] with h(x)=1, where the margin μ_h(x) of h at x∈[n] is defined as the largest non-negative integer a such that h is constant on the interval I_a(x)=[x-a,x+a]⊆[n]. Estimates are obtained for the cardinality of classes of binary-valued functions with a margin of at least N on a positive sample S⊆[n].     

Simple characterization of functionally complete one‐element sets of propositional connectives

A set of propositional connectives is said to be functionally complete if all propositional formulae can be expressed using only connectives from that set. In this paper we give sufficient and necessary conditions for a one‐element set of propositional connectives to be functionally complete. These conditions provide a simple and elegant characterization of functionally complete one‐element sets of propositional connectives (of arbitrary arity). (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Concatenating Indicators of Flats for Designing Cryptographic Functions

Boolean functions with good cryptographic characteristics are needed for the design of robust pseudo-random generators for stream ciphers and of S-boxes for block ciphers. Very few general constructions of such cryptographic Boolean functions are known. The main ones correspond to concatenating affine or quadratic functions. We introduce a general construction corresponding to the concatenation of indicators of flats. We show that the functions it permits to design can present very good cryptographic characteristics.     

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.