On the circuits reliability in “anticonjunction” basis with constant faults at gate inputs

We consider the implementation of Boolean functions by circuits consisting of unreliable functional gates in the basis which contains only anticonjunction. We assume that each circuit gate is exposed to the faults of type 0 or type 1 at the inputs. The circuits are constructed for all Boolean functions and the upper bound of their unreliability is found which depends only on the probabilities of appearance of type 0 fault and type 1 fault at the gate inputs. We also prove that the found upper bound of the circuits unreliability is asymptotically (for small values of probability) equals the lower bound of the unreliability for almost all Boolean functions.     

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     

Variable orderings and the size of OBDDs for random partially symmetric Boolean functions

The size of ordered binary decision diagrams (OBDDs) strongly depends on the chosen variable ordering. It is an obvious heuristic to use symmetric variable orderings, i.e., variable orderings where symmetric variables are arranged adjacently. In order to evaluate this heuristic, methods for estimating the OBDD size for random partially symmetric functions are presented. Characterizations of cases where, with high probability, only symmetric variable orderings and, with high probability, only nonsymmetric variable orderings lead to minimum OBDD size are obtained. For this analysis estimates for the number of different blocks of random Boolean matrices are used. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 49–70, 1998     

Symbolic topological sorting with OBDDs

We present a symbolic OBDD algorithm for topological sorting which requires O(log²|V|) OBDD operations. Then we analyze its true runtime for the directed grid graph and show an upper bound of O(log⁴|V|loglog|V|). This is the first true runtime analysis of a symbolic OBDD algorithm for a fundamental graph problem, and it demonstrates that one can hope that the algorithm behaves well for sufficiently structured inputs.     

MULTI-LEVEL ADAPTIVE CORRECTIONS IN FINITE DIMENSIONAL APPROXIMATIONS

Based on the Boolean sum technique, we introduce and analyze in this paper a class of multi-level iterative corrections for finite dimensional approximations. This type of multi-level corrections is adaptive and can produce highly accurate approximations. For illustration, we present some old and new finite element correction schemes for an elliptic boundary value problem.     

Maximal number of Boolean functions realized by an initial Boolean automaton with two constant states

The problem of realization of Boolean functions by initial Boolean automata with two constant states and n inputs is considered. An initial Boolean automaton with two constant states and n inputs is an initial automaton with output such that in all states the output functions are n-ary constant Boolean functions 0 or 1. The maximum cardinality of set of n-ary Boolean functions, where n > 1, realized by an initial Boolean automaton with two constant states and n inputs is obtained.     

The covering problem of complete uniform hypergraphs

A result of Krichevskii [3] and Hansel [1], concerning coverings of complete bipartite graphs is extended to hypergraphs, thus providing a lower bound on the lengths of Boolean formulas of a certain type realizing the threshold functions.     

Exact relations between nonlinearity and algebraic immunity

We sharpen some lower bounds on the higher order nonlinearity of a Boolean function in terms of the value of its algebraic immunity and obtain new tight bounds. We prove a universal tight lower bound, which enables us to reduce the problem of estimating higher order nonlinearity to finding the dimension of certain linear subspaces in the space of Boolean functions. As a simple corollary of this result, we obtain all previously known estimates in this area. For polynomials with disjoint terms, finding the dimension of those linear subspaces reduces to a simple combinatorial inspection. We prove a tight lower bound on the second order nonlinearity of a Boolean function in terms of the value of its algebraic immunity.     

Asymptotic solutions of inhomogeneous differential equations having a turning point

Asymptotic solutions are derived for inhomogeneous differential equations having a large real or complex parameter and a simple turning point. They involve Scorer functions and three slowly varying analytic coefficient functions. The asymptotic approximations are uniformly valid for unbounded complex values of the argument, and are applied to inhomogeneous Airy equations having polynomial and exponential forcing terms. Error bounds are available for all approximations, including new simple ones for the well-known asymptotic expansions of Scorer functions of large complex argument.     

-functionals and multivariate Bernstein polynomials

This paper estimates upper and lower bounds for the approximation rates of iterated Boolean sums of multivariate Bernstein polynomials. Both direct and inverse inequalities for the approximation rate are established in terms of a certain K-functional. From these estimates, one can also determine the class of functions yielding optimal approximations to the iterated Boolean sums.     

代数免疫度为1的布尔函数

布尔函数的代数免疫度是在流密码的代数攻击中所产生的重要概念.研究了代数免疫度为1的布尔函数,得到的主要结果有:对代数免疫度为1的布尔函数给出了一个谱刻画,给出了其个数的精确计数公式,最后给出了此类函数的非线性度的紧的上界.     

Estimates for the number of Boolean functions realized by an initial Boolean automaton with three constant states

The problem of realization of Boolean functions by initial Boolean automata with constant states and n inputs is considered. Such automata are those whose output function coincides with one of n-ary constant Boolean functions 0 or 1 in all states. The exact value of the maximum number of n-ary Boolean functions, where n > 1, realized by an initial Boolean automaton with three constant states and n inputs is obtained.     

On the nonlinearity of linear recurrence sequences

We obtain an upper bound on exponential sums of a new type with linear recurrence sequences. We apply this bound to estimate the Fourier coefficients, and thus the nonlinearity, of a Boolean function associated with a linear recurrence sequence in a natural way.     

A continuous approach to inductive inference

In this paper we describe an interior point mathematical programming approach to inductive inference. We list several versions of this problem and study in detail the formulation based on hidden Boolean logic. We consider the problem of identifying a hidden Boolean function:{0, 1} ⁿ {0, 1} using outputs obtained by applying a limited number of random inputs to the hidden function. Given this input—output sample, we give a method to synthesize a Boolean function that describes the sample. We pose the Boolean Function Synthesis Problem as a particular type of Satisfiability Problem. The Satisfiability Problem is translated into an integer programming feasibility problem, that is solved with an interior point algorithm for integer programming. A similar integer programming implementation has been used in a previous study to solve randomly generated instances of the Satisfiability Problem. In this paper we introduce a new variant of this algorithm, where the Riemannian metric used for defining the search region is dynamically modified. Computational results on 8-, 16- and 32-input, 1-output functions are presented. Our implementation successfully identified the majority of hidden functions in the experiment.     

A tighter variant of Jensen’s lower bound for stochastic programs and separable approximations to recourse functions

In this paper, we propose a new method to compute lower bounds on the optimal objective value of a stochastic program and show how this method can be used to construct separable approximations to the recourse functions. We show that our method yields tighter lower bounds than Jensen’s lower bound and it requires a reasonable amount of computational effort even for large problems. The fundamental idea behind our method is to relax certain constraints by associating dual multipliers with them. This yields a smaller stochastic program that is easier to solve. We particularly focus on the special case where we relax all but one of the constraints. In this case, the recourse functions of the smaller stochastic program are one dimensional functions. We use these one dimensional recourse functions to construct separable approximations to the original recourse functions. Computational experiments indicate that our lower bounds can significantly improve Jensen’s lower bound and our recourse function approximations can provide good solutions.     

Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case

We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not included in the class of monotone Boolean functions. For the particular case of symmetric functions our bounds are matching and we exactly characterize the best possible competitiveness achievable by a deterministic algorithm. Our upper bound is obtained by a simple polynomial time algorithm.     

Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms

The problem of constructing simple disjunctive normal forms (DNFs) of Boolean functions with a small number of zeros is considered. The problem is of interest in the complexity analysis of Boolean functions and in its applications to data analysis. The method used is a further development of the reduction approach to the construction of DNFs of Boolean functions. A key idea of the reduction method is that a Boolean function is represented as a disjunction of Boolean functions with fewer zeros. In a number of practically important cases, this technique makes it possible to considerably reduce the complexity of DNF implementations of Boolean functions.     

Upper estimate of unreliability of schemes in full finite basis (in <Emphasis Type="Italic">P</Emphasis><Subscript>2</Subscript>) for arbitrary faults of gates

We consider the realization of Boolean functions by circuits with unreliable functional gates in a complete finite basis. We assume that each gate of the circuit is exposed to arbitrarily faults, and the gates faults are statistically independent. We construct the circuits for all Boolean functions and get their upper bound of the unreliability, which depends on the “worst” (the most unreliable) of the basic gate.     

Complexity of tests checking the operation of logic diagram inputs

Exact upper bounds for the complexity of absolute tests checking the correctness of inputs of logic diagrams realizing Boolean functions which are essentially dependent on n variables have been found for n ≥ 136.     

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.