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.     

An improved working set selection for SMO-type decomposition method

The sequential minimization optimization (SMO) is a simple and efficient decomposition algorithm for solving support vector machines (SVMs). In this paper, an improved working set selection and a simplified minimization step are proposed for the SMO-type decomposition method that reduces the learning time for SVM and increases the efficiency of SMO. Since the working set is selected directly according to the Karush–Kuhn–Tucker (KKT) conditions, the minimization step of subproblem is simplified, accordingly the learning time for SVM is reduced and the convergence is accelerated. Following Keerthi’s method, the convergence of the proposed algorithm is analyzed. It is proven that within a finite number of iterations, solution that is based on satisfaction of the KKT conditions will be obtained by using the improved algorithm.     

Approximate decoupling of multivariate polynomials using weighted tensor decomposition

Many scientific and engineering disciplines use multivariate polynomials. Decomposing a multivariate polynomial vector function into a sandwiched structure of univariate polynomials surrounded by linear transformations can provide useful insight into the function while reducing the number of parameters. Such a decoupled representation can be realized with techniques based on tensor decomposition methods, but these techniques have only been studied in the exact case. Generalizing the existing techniques to the noisy case is an important next step for the decoupling problem. For this extension, we have considered a weight factor during the tensor decomposition process, leading to an alternating weighted least squares scheme. In addition, we applied the proposed weighted decoupling algorithm in the area of system identification, and we observed smaller model errors with the weighted decoupling algorithm than those with the unweighted decoupling algorithm.     

Generating Functions in the Knapsack Problem

The knapsack problem with Boolean variables and a single constraint is considered. Combinatorial formulas for calculating and estimating the cardinality of the set of feasible solutions and the values of the functional in various cases depending on given parameters of the problem are derived. The coefficients of the objective function and of the constraint vector and the knapsack size are used as parameters. The baseline technique is the classical method of generating functions. The results obtained can be used to estimate the complexity of enumeration and decomposition methods for solving the problem and can also be used as auxiliary procedures in developing such methods.     

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.     

用Adomian分解法求解分数阻尼梁的解析解

利用Adomian分解法, 得到了由任意阶分数微分描述的具有阻尼特性的黏弹性连续梁的解析解．解中包含了任意的初始条件和零输入．为了更明确的分析, 假定初始条件是奇次的,输入受力是针对某种特定梁的特殊过程．分别考虑了两种简单情况下梁的响应:阶跃激励和脉冲激励．然后在系统的不同组参数条件下绘制了梁的位移图,并且讨论了梁在不同微分阶数下响应情况．     

Algorithmic aspects of the substitution decomposition in optimization over relations,set systems and Boolean functions

In the last years, decomposition techniques have seen an increasing application to the solution of problems from operations research and combinatorial optimization, in particular in network theory and graph theory. This paper gives a broad treatment of a particular aspect of this approach, viz. the design of algorithms to compute the decomposition possibilities for a large class of discrete structures. The decomposition considered is thesubstitution decomposition (also known as modular decomposition, disjunctive decomposition, X-join or ordinal sum). Under rather general assumptions on the type of structure considered, these (possibly exponentially many) decomposition possibilities can be appropriately represented in acomposition tree of polynomial size. The task of determining this tree is shown to be polynomially equivalent to the seemingly weaker task of determining the closed hull of a given set w.r.t. a closure operation associated with the substitution decomposition. Based on this reduction, we show that for arbitrary relations the composition tree can be constructed in polynomial time. For clutters and monotonic Boolean functions, this task of constructing the closed hull is shown to be Turing-reducible to the problem of determining the circuits of the independence system associated with the clutter or the prime implicants of the Boolean function. This leads to polynomial algorithms for special clutters or monotonic Boolean functions. However, these results seem not to be extendable to the general case, as we derive exponential lower bounds for oracle decomposition algorithms for arbitrary set systems and Boolean functions.     

Computing in fault tolerant broadcast networks and noisy decision trees

We consider a fault tolerant broadcast network of n processors each holding one bit of information. The goal is to compute a given Boolean function on the n bits. In each step, a processor may broadcast one bit of information. Each listening processor receives the bit that was broadcast with error probability bounded by a fixed constant ?. The errors in different steps, as well as for different receiving processors in the same step, are mutually independent. The protocols that are considered in this model are oblivious protocols: At each step, the processors that broadcast are fixed in advanced and independent of the input and the outcome of previous steps. We present here the first linear complexity protocols for several classes of Boolean functions. This answer an open question of Yao (Invited talk in the 5th ISTCS Conf., 1997), considering this fault tolerant model that was introduced by El Gamal (Open problems presented at the 1984 workshop on Specific Problems in Communication and Computation sponsored by Bell Communication Research) and studied also by Gallager 10 . © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Natural gradient algorithm for stochastic distribution systems with output feedback

In this paper, we use natural gradient algorithm to control the shape of the conditional output probability density function for the stochastic distribution systems from the viewpoint of information geometry. The considered system here is of multi-input and single output with an output feedback and a stochastic noise. Based on the assumption that the probability density function of the stochastic noise is known, we obtain the conditional output probability density function whose shape is only determined by the control input vector under the condition that the output feedback is known at any sample time. The set of all the conditional output probability density functions forms a statistical manifold (M), and the control input vector and the output feedback are considered as the coordinate system. The Kullback divergence acts as the distance between the conditional output probability density function and the target probability density function. Thus, an iterative formula for the control input vector is proposed in the sense of information geometry. Meanwhile, we consider the convergence of the presented algorithm. At last, an illustrative example is utilized to demonstrate the effectiveness of the algorithm.     

Inferring Boolean functions via higher-order correlations

Both the Walsh transform and a modified Pearson correlation coefficient can be used to infer the structure of a Boolean network from time series data. Unlike the correlation coefficient, the Walsh transform is also able to represent higher-order correlations. These correlations of several combined input variables with one output variable give additional information about the dependency between variables, but are also more sensitive to noise. Furthermore computational complexity increases exponentially with the order. We first show that the Walsh transform of order 1 and the modified Pearson correlation coefficient are equivalent for the reconstruction of Boolean functions. Secondly, we also investigate under which conditions (noise, number of samples, function classes) higher-order correlations can contribute to an improvement of the reconstruction process. We present the merits, as well as the limitations, of higher-order correlations for the inference of Boolean networks.     

An Algorithm to Construct Gilbert's Decomposition and Its Implementation for the Circuit Design Problem

An algorithm is proposed for the construction of monotone Boolean functions M ₀, M ₁,..., M _k in the decomposition of the Boolean function _f or some extension of f. The decomposition is applied to implement a circuit design algorithm that evaluates f in real LSI microelectronics devices. __________ Translated from Prikladnaya Matematika i Informatika, No. 18, pp. 108–121, 2004.     

On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

Representations of Boolean functions by exclusive-OR sums (modulo 2) of pseudoproducts is studied. An ExOR-sum of pseudoproducts (ESPP) is the sum modulo 2 of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this form, and the length of a Boolean function in the class of ESPPs is defined as the minimum length of an ESPP representing this function. The Shannon function L ^ESPP(n) of the length of Boolean functions in the class of ESPPs is considered, which equals the maximum length of a Boolean function of n variables in this class. Lower and upper bounds for the Shannon function L ^ESPP(n) are found. The upper bound is proved by using an algorithm which can be applied to construct representations by ExOR-sums of pseudoproducts for particular Boolean functions.     

基于矩阵模型表示的(线性)有限自动机的同步序列判定

在有限自动机矩阵模型表示方法的基础上,采用矩阵理论和布尔代数为工具,分别给出了判定输入序列是否是(线性)有限自动机的同步序列的新充要条件和求解线性有限自动机的最短同步序列的新算法.     

Polynomial Reproduction in Subdivision

We study conditions on the matrix mask of a vector subdivision scheme ensuring that certain polynomial input vectors yield polynomial output again. The conditions are in terms of a recurrence formula for the vectors which determine the structure of polynomial input with this property. From this recurrence, we obtain an algorithm to determine polynomial input of maximal degree. The algorithm can be used in the design of masks to achieve a high order of polynomial reproduction.     

Performance of derivative free search ANN training algorithm with time series and classification problems

A Manhattan search algorithm to minimize artificial neural network error function is outlined in this paper. From an existing position in Cartesian coordinate, a search vector moves in orthogonal directions to locate minimum function value. The search algorithm computes optimized step length for rapid convergence. This step is performed when consecutive search is successful in minimizing function value. The optimized step length identifies favorable descent direction to minimize function value. The search method is suitable for complex error surface where derivative information is difficult to obtain or when the error surface is nearly flat. The rate of change in function value is almost negligible near the flat surface. Most of the derivative based training algorithm faces difficulty in such scenarios. This algorithm avoids derivative information of an error function. Therefore, it is an attractive search method when derivative based algorithm faces difficulty due to complex ridges and flat valleys. In case the algorithm gets into trapped minimum, the search vector takes steps to move out of a local minimum by exploring neighborhood descent search directions. The algorithm differs from the first and second order derivative based training methods. To measure the performance of the algorithm, estimation of electric energy generation model from Fiji Islands and “L-T” letter recognition problems are solved. Bootstrap analysis shows that the algorithm’s predictive and classification abilities are high. The algorithm is reliable when solution to a problem is unknown. Therefore, the algorithm identifies benchmark solution.     

Iterated Boolean functions in the elementary basis

We establish a new criterion for a Boolean function to be read-once over the basis of conjunction, disjunction, and negation. We prove that each Boolean function is either read-once or has a set of four or six input vectors such that values of this function on these vectors show that it is iterated. We use this criterion to deduce an alternative proof of the known Stetsenko criterion.     

On the complexity of the dualization problem

The computational complexity of discrete problems concerning the enumeration of solutions is addressed. The concept of an asymptotically efficient algorithm is introduced for the dualization problem, which is formulated as the problem of constructing irreducible coverings of a Boolean matrix. This concept imposes weaker constraints on the number of “redundant” algorithmic steps as compared with the previously introduced concept of an asymptotically optimal algorithm. When the number of rows in a Boolean matrix is no less than the number of columns (in which case asymptotically optimal algorithms for the problem fail to be constructed), algorithms based on the polynomialtime-delay enumeration of “compatible” sets of columns of the matrix is shown to be asymptotically efficient. A similar result is obtained for the problem of searching for maximal conjunctions of a monotone Boolean function defined by a conjunctive normal form.     

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.     

An incremental primal–dual method for nonlinear programming with special structure

We propose a new class of incremental primal–dual techniques for solving nonlinear programming problems with special structure. Specifically, the objective functions of the problems are sums of independent nonconvex continuously differentiable terms minimized subject to a set of nonlinear constraints for each term. The technique performs successive primal–dual increments for each decomposition term of the objective function. The primal–dual increments are calculated by performing one Newton step towards the solution of the Karush–Kuhn–Tucker optimality conditions of each subproblem associated with each objective function term. We show that the resulting incremental algorithm is q-linearly convergent under mild assumptions for the original problem.