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

The depth of Boolean functions realized by circuits over an arbitrary basis

Realization of Boolean functions by circuits of functional elements is considered over arbitrary complete bases (including infinite ones). The depth of a circuit means the maximal number of functional elements forming an oriented chain going from inputs of the circuit to its output. It is shown that for any basis B the growth order of the Shannon function of depth D _B (n) for n → ∞ is equal to 1, log₂ n, or n, and the latter case appears if and only if the basis B is finite.     

Depth of Boolean functions over an arbitrary infinite basis

Realization of Boolean functions by circuits is considered over an arbitrary infinite complete basis. The depth of a circuit is defined as the greatest number of functional elements constituting a directed path from an input of the circuit to its output. The Shannon function of the depth is defined for a positive integer n as the minimal depth D _B (n) of the circuits sufficient to realize every Boolean function on n variables over a basis B. It is shown that, for each infinite basis B, either there exists a constant β ? 1 such that D _B (n) = β for all sufficiently large n or there exist an integer constant γ ? 2 and a constant δ such that log _γ n ? D _B (n) ? log _γ n + δ for all n.     

Network delay in a model with inputs of functional elements

We consider a model of delays in networks of functional elements in an arbitrary finite complete basis B, where the delays of basis elements are arbitrary positive real numbers for each input and each input set of variables going to the remaining inputs. This model estimates the delays in a multiplexer function of nth order asymptotically as τ_B n ± O(logn), where τ_B is a constant depending only on the basis B. On the basis of these estimates and within this model, asymptotic estimates of the form τ_B n ± O(logn) are obtained for the corresponding Shannon function, i.e., for the delay of the “worst” Boolean algebra function of given n variables.     

On the Complexity and Depth of Embedded in Boolean Cube Circuits That Implement Boolean Functions

A class of circuits of functional elements over the standard basis of the conjunction, disjunction, and negation elements is considered. For each circuit Σ in this class, its depth D(Σ) and dimension R(Σ) equal to the minimum dimension of the Boolean cube allowing isomorphic embedding Σ are defined. It is established that for n = 1, 2,… and an arbitrary Boolean function f of n variables there exists a circuit Σ_f for implementing this function such that R(Σ_f) ? n ? log₂ log₂n + O(1) and D(Σ_f) ? 2n ? 2 log₂ log₂n + O(1). It is proved that for n = 1, 2,… almost all functions of n variables allow implementation by circuits of the considered type, whose depth and dimension differ from the minimum values of these parameters (for all equivalent circuits) by no more than a constant and asymptotically no more than by a factor of 2, respectively.     

Upper bounds for the formula size of symmetric Boolean functions

We prove that the complexity of the implementation of the counting function of n Boolean variables by binary formulas is at most n ^3.03, and it is at most n ^4.47 for DeMorgan formulas. Hence, the same bounds are valid for the formula size of any threshold symmetric function of n variables, particularly, for the majority function. The following bounds are proved for the formula size of any symmetric Boolean function of n variables: n ^3.04 for binary formulas and n ^4.48 for DeMorgan ones. The proof is based on the modular arithmetic.     

Circuits asymptotically optimal in reliability in special bases

We consider realization of Boolean functions by the circuits composed of unreliable elements in a complete basis B ? B ₃ (with B ₃ the set of all Boolean functions of three variables x ₁, x ₂, and x ₃). We assume that, with probability ? ∈ (0, 1/2), all elements of a circuit are independently subjected to inverse failures at outputs. All bases are found in which it is possible to realize almost all Boolean functions by the circuits asymptotically optimal in reliability and functioning with unreliability 3? as ? → 0. It is proved that there are no other bases B ? B ₃ like these.     

Synthesis of easily tested circuits in some infinite basis

It is constructively established in the paper that in the case of constant faults on outputs of elements any Boolean function of n variables may be implemented by a circuit of functional elements in some infinite basis admitting a unitary diagnostic test whose length does not exceed 2 log₂?n + 1? + 1.     

Delays of schemes in a model that considers the input values of functional elements

A delay model for schemes of functional elements in arbitrary finite complete basis B is studied; in the model, delays of the basic element are given by random positive real numbers for each input and each input set of variables entering other inputs. Asymptotic estimates in the form τ_B n ± O(logn), where τ_B is a constant that depends only on basis B, are obtained for the delay of the multiplex function of order n. Based on these estimates, asymptotic estimates of the form τ_B n ± O(logn) for the corresponding Shannon function, i.e., for the delay of the worst function of logic algebra that depends on given n variables, are established.     

On bases with unreliability coefficient 2

Consider the realization of Boolean functions by networks from unreliable functional components in a complete basis B ? B ₃ (B ₃ is the set of all Boolean functions depending on the variables x ₁, x ₂, x ₃). It is assumed that all the components of the network are subject to inverse faults at the outputs independently of each other with probability ? ∈ (0, 1/2). In B ₃, we obtain all complete bases in which the following two conditions simultaneously hold: 1) any function can be realized by a network with unreliability asymptotically not greater than 2? (? → 0); 2) there exist functions (denote their set by K) that cannot be realized by networks with unreliability asymptotically less than 2?, ? → 0. Such bases will be called bases with unreliability coefficient 2. It is also proved that the set K contains almost all functions.     

Depth of functions of k-valued logic in finite bases

Realization of functions of the k-valued logic by circuits is considered over an arbitrary finite complete basis B. Asymptotic behavior of the Shannon function D _B (n) of the circuit depth over B is examined. The value D _B (n) is the minimal depth sufficient to realize every function of the k-valued logic of n variables by a circuit over B. It is shown that for each natural k ≥ 2 and for any finite complete basis B there exists a positive constant α _B such that D _B (n) ～ α _B n for n → ∞.     

Depth of functions of the <Emphasis Type="Italic">k</Emphasis>-valued logic in infinite bases

The realization of functions of the k-valued logic by circuits is considered over an arbitrary infinite complete basis B. The Shannon function D _B (n) of the circuit depth over B is examined (for any positive integer n the value D _B (n) is the minimal depth sufficient to realize every function of the k-valued logic of n variables by a circuit over B). It is shown that for each fixed k ≥ 2 and for any infinite complete basis B either there exists a constant α ≥ 1 such that D _B (n) = α for all sufficiently large n, or there exist constants β (β > 0), γ, δ such that βlog₂ n ≤ D _B (n) ≤ γlog₂ n + δ for all n.     

Sharpening an upper bound on the adder and comparator depths

The upper bound log₂ n + log₂ log₂ n + const is proved on the depth of the addition and comparison operators on n-bit numbers over the basis {&;, ∨, ～}.     

Lower Bounds on the Depth of Monotone Arithmetic Computations

Consider an arithmetic expression of lengthninvolving only the operations {+, ×} and non-negative constants. We prove lower bounds on the depth of any binary computation tree over the same sets of operations and constants that computes such an expression. We exhibit a family of arithmetic expressions that requires computation trees of depth at least 1.5 log₂ n−O(1), thus proving a conjecture of S. R. Kosaraju (1986,in“Proc. of the 18th ACM Symp. on Theory Computing,” pp. 231–239). In contrast, Kosaraju showed how to compute such expressions with computation trees of depth 2 log₂ n+O(1).     

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

One Approach to synthesizing predicate circuits on the basis of generalized variables

The asymptotic behavior of the Shannon’s function L _B(n) is studied for complexity of n-variable predicate implementation with the use of predicate circuits over arbitrary complete basis B. A new definition of the reduced weight of the predicate is introduced, regarding it as a solution of a specific linear programming problem based on a system of predicate’s generalized variables. New, more exact upper elements for L _B(n) in a number of bases are acquired by the means of special decompositions of initial predicates using universal sets of predicates constructed for circuits consisting of bases elements with minimal reduced weight.     

An Efficient Algorithm for the Complex Roots Problem

Given a univariate polynomialf(z) of degreenwith complex coefficients, whose norms are less than 2^min magnitude, the root problem is to find all the roots off(z) up to specified precision 2^−μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexityO(nlog⁵nlogB), whereb= χ + μ, and χ = max{n,m}. This improves on the previous best known algorithm of Pan for the problem, which has complexityO(n²log²nlog(m+ μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation off, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = ⌈n(B+ logn+ 3)⌉ bits of the binary representations of the real and imaginary parts of each of the coefficients off. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where[formula]and[formula]Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor ofM(φ) (whereM(ψ) =O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and “centered” points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel timeO(log⁶nlogB) usingnprocessors.     

On a continuous analogue of the stochastic difference equation Xn=ρXn-1+Bn

Let B₁, B₂, ... be a sequence of independent, identically distributed random variables, letX₀ be a random variable that is independent ofB_n forn?1, let ρ be a constant such that 0<ρ<1 and letX₁,X₂, ... be another sequence of random variables that are defined recursively by the relationshipsX_n=ρX_n-1+B_n. It can be shown that the sequence of random variablesX₁,X₂, ... converges in law to a random variableX if and only ifE[log⁺¦B₁¦]<∞. In this paper we let {B(t):0≦t<∞} be a stochastic process with independent, homogeneous increments and define another stochastic process {X(t):0?t<∞} that stands in the same relationship to the stochastic process {B(t):0?t<∞} as the sequence of random variablesX₁,X₂,...stands toB₁,B₂,.... It is shown thatX(t) converges in law to a random variableX ast →+∞ if and only ifE[log⁺¦B(1)¦]<∞ in which caseX has a distribution function of class L. Several other related results are obtained. The main analytical tool used to obtain these results is a theorem of Lukacs concerning characteristic functions of certain stochastic integrals.     

Asymptotics of the probability of values of random Boolean expressions

The random Boolean expressions are considered that are obtained by the random and independent substitution with the probabilities p and 1 ? p of the constantly one function and constantly zero function for variables of repetition-free formulas over a given basis. The probability is studied that the expressions are equal to one. It is shown that, for each finite basis and p ? (0, 1), this probability tends to some finite limit P ₁(p) as the length of an expression grows. Explicit representation of the probability function P ₁(p) is found for all finite bases, the analytic properties of this function are studied, and its behavior is investigated in dependence on the properties of the basis.