The Boolean functions computed by random Boolean formulas or how to grow the right function

We characterize growth processes (probabilistic amplification) by their initial conditions to derive conditions under which results such as Valiant's 24 hold. We completely characterize growth processes that use linear connectives and generalize Savický's 19 analysis to characterize growth processes that use monotone connectives. Additionally, we obtain explicit bounds on the convergence rates of several growth processes, including the growth process studied in Savický. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

On a class of holomorphic functions representable by Carleman formulas in the interior of an equilateral cone from their values on its rigid base

Let Δ be an equilateral cone in C with vertices at the complex numbers and rigid base M (Section 1). Assume that the positive real semi-axis is the bisectrix of the angle at the origin. For the base M of the cone Δ we derive a Carleman formula representing all those holomorphic functions from their boundary values (if they exist) on M which belong to the class . The class is the class of holomorphic functions in Δ which belong to the Hardy class near the base M (Section 2). As an application of the above characterization, an important result is an extension theorem for a function fL¹(M) to a function .     

Realization of Boolean functions by formulas in continuous bases containing a continuum of constants

For an arbitrary Boolean function of n variables, we show how to construct formulas of complexity O(2 ^n/2) in the bases $$\left\{ {x - y,xy,\left| x \right|} \right\}\bigcup {\left[ {0,1} \right], } \left\{ {x - y,x*y,2x,\left| x \right|} \right\}\bigcup {\left[ {0,1} \right],}$$ , where x * y = max(?1, min(1, x))max(?1, min(1, y)). The obtained estimates are, in general, order-sharp.     

Generating cryptographically strong Boolean functions using partial information

Periodica Mathematica Hungarica - In our paper we study the usage of partially defined Boolean functions (PDBFs) for generating cryptographically strong Boolean functions. A PDBF can be considered...     

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.     

Multiplication formulas for Kubert functions

The aim of this paper is two folds. First, we shall prove a general reduction theorem to the Spannenintegral of products of （generalized） Kubert functions. Second, we apply the special case of Carlitz＇s theorem to the elaboration of earlier results on the mean values of the product of Dirichlet L-functions at integer arguments. Carlitz＇s theorem is a generalization of a classical result of Nielsen in 1923. Regarding the reduction theorem, we shall unify both the results of Carlitz （for sums） and Mordell （for integrals）, both of which are generalizations of preceding results by Frasnel, Landau, Mikolas, and Romanoff et al. These not only generalize earlier results but also cover some recent results. For example, Beck＇s lamma is the same as Carlitz＇s result, while some results of Maier may be deduced from those of Romanoff. To this end, we shall consider the Stiletjes integral which incorporates both sums and integrals. Now, we have an expansion of the sum of products of Bernoulli polynomials that we may apply it to elaborate on the results of afore-mentioned papers and can supplement them by related results.     

Linear codes from vectorial Boolean power functions

In this paper, three classes of binary linear codes with few weights are proposed from vectorial Boolean power functions, and their weight distributions are completely determined by solving certain equations over finite fields. In particular, a class of simplex codes and a class of first-order Reed-Muller codes can be obtained from our construction by taking the identity map, whose dual codes are Hamming codes and extended Hamming codes, respectively.     

Numerical computation of characteristic polynomials of Boolean functions and its applications

We study the problem of evaluation of characteristic polynomials of Boolean functions with applications to combinational circuit verification. Two Boolean functions are equivalent if and only if their corresponding characteristic polynomials are identical. However, to verify the equivalence of two Boolean functions it is often impractical to construct the corresponding characteristic polynomials due to a possible exponential blow-up of the terms of the polynomials. Instead, we compare their values at a sample point without explicitly constructing the characteristic polynomials. Specifically, we sample uniformly at random in a unit cube and determine whether two characteristic polynomials are identical by their evaluations at the sample point; the error probability is zero when there are no round-off errors. In the presence of round-off errors, we sample on regular grids and analyze the error probability. We discuss in detail the Shannon expansion for characteristic polynomial evaluation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Complexity of implementation of Boolean functions by real formulas

Upper complexity estimates are proved for implementation of Boolean functions by formulas in bases consisting of a finite number of continuous real functions and a continuum of constants. For some bases upper complexity estimates coincide with lower ones.     

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.     

布尔“复合函数”的Walsh循环谱和自相关函数

本文利用布尔随机变量联合分布的分解式给出了布尔“复合函数”和某布尔函数符合率的分解算式,由此求得了布尔“复合函数”的 Walsh循环谱和自相关函数的计算公式,公式清楚地表明了“复合”所得布尔函数的 Walsh循环谱与起“复合”作用的函数和被“复合”的各函数所有线性组合的 Walsh循环谱之间的关系、“复合”所得布尔函数的自相关函数与起“复合”作用的函数谱和被“复合”的各函数的谱及相关函数之间的关系,这两个公式在布尔函数的密码学性质研究中会有广泛的应用.     

Further properties of several classes of Boolean functions with optimum algebraic immunity

Based on a method proposed by the first author, several classes of balanced Boolean functions with optimum algebraic immunity are constructed, and they have nonlinearities significantly larger than the previously best known nonlinearity of functions with optimal algebraic immunity. By choosing suitable parameters, the constructed n-variable functions have nonlinearity for even for odd n, where Δ(n) is a function increasing rapidly with n. The algebraic degrees of some constructed functions are also discussed.      

On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2

We improve parts of the results of [T. W. Cusick, P. Stanica, Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Mathematics 258 (2002) 289-301; J. Pieprzyk, C. X. Qu, Fast hashing and rotation-symmetric functions, Journal of Universal Computer Science 5 (1) (1999) 20-31]. It is observed that the n-variable quadratic Boolean functions, for , which are homogeneous rotation symmetric, may not be affinely equivalent for fixed n and different choices of s. We show that their weights and nonlinearity are exactly characterized by the cyclic subgroup 〈s−1〉 of Z_n. If , the order of s−1, is even, the weight and nonlinearity are the same and given by . If the order is odd, it is balanced and nonlinearity is given by .     

Approximation of almost periodic functions by periodic ones

It is not the purpose of this paper to construct approximations but to establish a class of almost periodic functions which can be approximated, with an arbitrarily prescribed accuracy, by continuous periodic functions uniformly on =(+).     

Boolean constant degree functions on the slice are juntas

We show that a Boolean degree $d$ function on the “slice” $\left(\genfrac{}{}{0ex}{}{\left[n\right]}{k}\right)?\{(x_1,\dots ,x_n)\in \{0,1\}:{\sum }_{i=1}^n{x}_i=k\}$ is a junta (depends on a constant number $\gamma \left(d\right)$ of coordinates), assuming that $k,n?k$ are large enough. This generalizes a classical result of Nisan and Szegedy on the hypercube ${\{0,1\}}^n$. Moreover, we show that the maximum number of coordinates that a Boolean degree $d$ function can depend on is the same on the slice and on the hypercube.     

Realization of Boolean functions by combinational circuits embedded in the hypercube

In recent years, it has become popular to realize Boolean functions by combinational circuits. In many cases, the further use of the scheme constructed requires its geometric realization, i.e., a certain embedding in one or another specific geometric structure. The role of such structure is often played by the unit n-dimensional cube.In this paper, we consider quasihomeomorphic embeddings of combinational circuits in hypercubes such that the nodes of the scheme go into vertices of the hypercube and bundles of arcs go into similar bundles or the so-called transition trees of the hypercube having no common internal vertices.

Let B be a finite complete basis of functional elements and R _B(n) be the minimum dimension of a hypercube such that, for any function f(x ₁, …, x _n ) of Boolean logic, there is a certain scheme of functional elements in basis B realizing f(x ₁, …, x _n ) which can be quasihomeomorphically embedded in this cube. The main result of this work consists in derivation of the following estimates:

$n - \log \log (n) - c_B \leqslant R_B (n) \leqslant n - \log \log (n) + c'_B .$

Here, c _B and c′_B are basis-dependent constants.