Quantitative relation between noise sensitivity and influences

A Boolean function f: {0,1} ⁿ → {0,1} is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm [3] showed that if the sum of squares of inuences of f is close to zero then f must be noise sensitive. We show a quantitative version of this result which does not depend on n, and prove that it is tight for certain parameters. Our results hold also for a general product measure µ _p on the discrete cube, as long as log1/p?logn. We note that in [3], a quantitative relation between the sum of squares of the inuences and the noise sensitivity was also shown, but only when the sum of squares is bounded by n ^?c for a constant c. Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions. In order to achieve it, we present a considerably shorter proof of Talagrand’s lemma, which easily generalizes in various directions, including non-monotone functions.     

Convex subsets of 2n and bounded truth-table reducibility

Let 2ⁿ be the set of n-tuples of 0's and 1's, partially ordered componentwise. A characterization is given of the possible decompositions of arbitrary subsets of 2ⁿ as disjoint unions of sets which are convex in this ordering; this result is used to obtain a decomposition theorem for Boolean functions in terms of monotone functions. The second half of the paper contains applications to recursion theory; in particular, canonical forms for certain minimum-norm bounded-truth-table reductions are obtained.     

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.     

Complexity of the Realization of a Linear Boolean Function in the Class of <Emphasis Type="Italic">π</Emphasis>-Schemes

Using Khrapchenko’s method, we obtain the exact lower bound of 40 for the complexity in the class of π-schemes of a linear Boolean function depending substantially on 6 variables. We give a simplified proof of several lower bounds for the complexity of linear Boolean functions which are previously obtained on the basis of the same method.     

The Pjateckiĭ-S̆apiro prime number theorem

It is proved that the sequence [n^c] contains the expected number of primes whenever 1 < c < 1.1404…, thus improving Kolesnik's range 1 < c < 1.1111…. An identity of Vaughan's type in five variables is needed.     

On the complexity of growth of the number of distinct fuzzy switching functions

Several attempts have been made to enumerate fuzzy switching (FSF's) and to develop upper and lower bounds for the number of FSF's of n variables in an effort to better understand the properties and the complexity of FSF's. Previous upper bounds are 2⁴ⁿ [9] and 2^{2–3n—2n—1} [7].It has also been shown that the exact numbers of FSF's of n variables for n = 0, 1, 2, 3, and 4 are 2, 6, 8, 84, 43 918 and 160 297 985 276 respectively.This paper will give a brief overview of previous approaches to the problem, study some of the properties of fuzzy switching functions and give improved upper and lower bounds for a general n.     

Complexity of linear and majority functions in the basis of antichain functions

The complexity of realization of Boolean functions by circuits of functional elements in the basis consisting of all characteristic functions of antichains over a Boolean cube is studied. It is proved that the complexity of realization of an n-variable parity function is \(\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor \) and the complexity of its negation equals the complexity of the n-variable majority function which is \(\left\lceil {\frac{{n + 1}}{2}} \right\rceil \).     

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.     

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.     

The 1-width of (0,1)-matrices having constant row sum 3

In this note we establish upper bounds for the 1-width of an m × n matrix of 0's and 1's having three 1's in every row and having a constant number, c, of 1's in every column. When c = 3, this upper bound is $\text{n}\text{2}$ and when c = 4 this estimate is $\text{5n}\text{9}$. In these cases the upper bound is best possible, in the sense that for every possible size there exist matrices with this maximal 1-width. The technique of proof is also used to improve the known bound for the 1-width of (0, 1)-matrices with constant line sum 4.     

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

Depth of <Emphasis Type="Italic">α</Emphasis>-completions of systems of Boolean functions

A problem of realization of Boolean functions by α-formulas is considered. These formulas are such that each subformula contains not more than one nontrivial principal subformula. The depth is considered as a complexity measure of a formula. Upper and lower polynomial estimates of Shannon functions for α-completions of finite systems of Boolean functions are obtained.     

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.     

Complexity of fixed points, I

We study the complexity (minimal cost) of computing an s-approximation to a fixed point of a contractive function with the contractive factor q < 1. This is done for the relative error criterion in Part I and for the absolute error criterion in Part II, which is in progress. The complexity depends strongly on the dimension of the domain of functions. For the one-dimensional case we develop an optimal fixed point envelope (FPE) algorithm. The cost of the FPE algorithm with use of the relative error criterion is roughly , where c is the cost of one function evaluation. Thus, for fixed ε and q close to 1 the cost of the FPE algorithm is much smaller than the cost of the simple iteration algorithm, since the latter is roughly For the contractive functions of d variables, with d ≥ log(1/ε)/log(l/q) we show that it is impossible to essentially improve the efficiency of the simple iteration.     

Noise sensitivity in continuum percolation

We prove that the Poisson Boolean model, also known as the Gilbert disc model, is noise sensitive at criticality. This is the first such result for a Continuum Percolation model, and the first which involves a percolation model with critical probability p _c ≠ 1/2. Our proof uses a version of the Benjamini-Kalai-Schramm Theorem for biased product measures. A quantitative version of this result was recently proved by Keller and Kindler. We give a simple deduction of the non-quantitative result from the unbiased version. We also develop a quite general method of approximating Continuum Percolation models by discrete models with p _c bounded away from zero; this method is based on an extremal result on non-uniform hypergraphs.     

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.     

On complexity of round transformations

A modern block cipher consists of round transformations, which are obtained by alternatively applying permutations (P-boxes) and substitutions (S-boxes). Clearly, the most important attribute of a block cipher is its security. However, with respect to the hardware implementation, a good block cipher has to have a reasonable complexity as well. In this paper, we study complexity of round transformations satisfying some basic security criteria. There are several ways to define the complexity of a round transformation, and to choose “necessary” security criteria. It turns out, that for our purpose, it is suitable to view a round transformation as a single Boolean function, not separating it into S-boxes and P-boxes. We require that the Boolean function F possesses some fundamental properties imposed on each block cipher for security reasons; namely, we require that the function is a strictly non-linear bijection and that it has a good diffusion. The total number of variables in the normal algebraic form of the component functions of F is taken as its complexity. We find the minimum complexity of such functions, and this way we establish a lower bound on complexity of all round transformations. To show that the lower bound is the best possible, we construct a round transformation F^′ attaining the bound. We stress that it is not an aspiration of this paper to construct a round transformation which would be of practical use; F^′ is useful only from the theoretical point of view.     

Patterson-Wiedemann construction revisited

In 1983, Patterson and Wiedemann constructed Boolean functions on n=15 input variables having nonlinearity strictly greater than 2^n-1-2^(n-1)/2. Construction of Boolean functions on odd number of variables with such high nonlinearity was not known earlier and also till date no other construction method of such functions are known. We note that the Patterson-Wiedemann construction can be understood in terms of interleaved sequences as introduced by Gong in 1995 and subsequently these functions can be described as repetitions of a particular binary string. As example we elaborate the cases for n=15,21. Under this framework, we map the problem of finding Patterson-Wiedemann functions into a problem of solving a system of linear inequalities over the set of integers and provide proper reasoning about the choice of the orbits. This, in turn, reduces the search space. Similar analysis also reduces the complexity of calculating autocorrelation and generalized nonlinearity for such functions. In an attempt to understand the above construction from the group theoretic view point, we characterize the group of all GF(2)-linear transformations of GF(2^ab) which acts on PG(2,2^a).     

Approximation of Boolean functions to Schaefer’s classes

We consider an algorithm for transferring Boolean functions to function classes for which the generalized satisfiability problem is solvable in polynomial time (Schaefer??s classes). For the case where an initial function is represented as a truth-table, it is proved that the complexity of the algorithm is $ {l^2} + l\,\log_2^2(l) $ , where l is the input length.