Search

The paper is focused on the implementation of parity functions by circuits in the basis . This basis consists of all gates that implement functions of the form . It is proved that every circuit in implementing a parity function of variables contains at least gates. [ABSTRACT FROM AUTHOR]

A sequential dynamical system (SDS) consists of a graph G with vertices v 1 , … , v n , a state set A , a collection of “vertex functions” { f v i } i = 1 n , and a permutation π ∈ S n that specifies how to compose these functions to yield the SDS map [ G , { f v i } i = 1 n , π ] : A n → A n . In this paper, we study symmetric invertible SDS defined over the cycle graph C n using the set of states F 2 . These are, in other words, asynchronous elementary cellular automata (ECA) defined using ECA rules 150 and 105. Each of these SDS defines a group action on the set F 2 n of n -bit binary vectors. Because the SDS maps are products of involutions, this relates to generalized toggle groups , which Striker recently introduced. In this paper, we further generalize the notion of a generalized toggle group to that of a flexible toggle group ; the SDS maps we consider are examples of Coxeter elements of flexible toggle groups. Our main result is the complete classification of the dynamics of symmetric invertible SDS defined over cycle graphs using the set of states F 2 and the identity update order π = 123 ⋯ n . More precisely, if T denotes the SDS map of such an SDS, then we obtain an explicit formula for | Per r ( T ) | , the number of periodic points of T of period r , for every positive integer r . It turns out that if we fix r and vary n and T , then | Per r ( T ) | only takes at most three nonzero values. [ABSTRACT FROM AUTHOR]

Each Boolean function can be computed by a single-pass instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. Auxiliary Boolean registers are not necessary for this. In the current paper, we show that, in the case of the parity functions, shorter instruction sequences are possible with the use of an auxiliary Boolean register in the presence of instructions to complement the content of auxiliary Boolean registers. This result supports, in a setting where programs are instruction sequences acting on Boolean registers, a basic intuition behind the storage of auxiliary data, namely the intuition that this makes possible a reduction of the size of a program. The work presented in this paper is carried out in the setting of PGA (ProGram Algebra) [ABSTRACT FROM AUTHOR]

The paper is concerned with circuits in the basis {x →y ,x̅}. The exact value of the complexity of implementation of an even parity function is obtained and the minimal circuits implementing an odd parity function are described [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider a logic circuit (i.e., a combinatorial circuit consisting of gates, each of which computes a Boolean function) computing a symmetric Boolean function , and investigate a relationship between two complexity measures, energy and fan-in of , where the energy is the maximum number of gates outputting “1” over all inputs to , and the fan-in is the maximum number of inputs of every gate in . We first prove that any symmetric Boolean function of variables can be computed by a logic circuit of energy and fan-in , and then provide an almost tight lower bound where is the maximum numbers of consecutive “0”s or “1”s in the value vector of . Our results imply that there exists a tradeoff between the energy and fan-in of logic circuits computing a symmetric Boolean function. [Copyright &y& Elsevier]

Abstract: A unate gate is a logical gate computing a unate Boolean function, which is monotone in each variable. Examples of unate gates are AND gates, OR gates, NOT gates, threshold gates, etc. A unate circuit is a combinatorial logic circuit consisting of unate gates. Let be a symmetric Boolean function of variables, such as the Parity function, MOD function, and Majority function. Let and be the maximum numbers of consecutive 0’s and consecutive 1’s in the value vector of , respectively, and let and . Let be a unate circuit computing . Let be the size of the circuit , that is, consists of unate gates. Let be the energy of , that is, is the maximum number of gates outputting “1” over all inputs to . In this paper, we show that there is a tradeoff between the size and the energy of . More precisely, we show that . We also present lower bounds on the size of represented in terms of , and . Our tradeoff immediately implies that for every unate circuit computing the Parity function of variables. [ABSTRACT FROM AUTHOR]

The family of decision tree learning algorithms is among the most widespread and studied. Motivated by the desire to develop learning algorithms that can generalize when learning highly varying functions such as those presumably needed to achieve artificial intelligence, we study some theoretical limitations of decision trees. We demonstrate formally that they can be seriously hurt by the curse of dimensionality in a sense that is a bit different from other nonparametric statistical methods, but most importantly, that they cannot generalize to variations not seen in the training set. This is because a decision tree creates a partition of the input space and needs at least one example in each of the regions associated with a leaf to make a sensible prediction in that region. A better understanding of the fundamental reasons for this limitation suggests that one should use forests or even deeper architectures instead of trees, which provide a form of distributed representation and can generalize to variations not encountered in the training data. [ABSTRACT FROM AUTHOR]

We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over {0;1}n. We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem in coding theory. This is the first evidence that attribute-efficient learning of a natural PAC learnable concept class can be computationally hard. An algorithm is said to use membership queries (MQs) non-adaptively if the points at which the algorithm asks MQs do not depend on the target concept. Using a simple non-adaptive parity learning algorithm and a modification of Levin's algorithm for locating a weakly-correlated parity due to Bshouty et al. (1999), we give the first non-adaptive and attribute-efficient algorithm for learning DNF with respect to the uniform distribution. Our algorithm runs in time Õ(ns4/ε) and uses Õ(s4 · log² n/ε) non-adaptive MQs, where s is the number of terms in the shortest DNF representation of the target concept. The algorithm improves on the best previous algorithm for learning DNF (of Bshouty et al., 1999) and can also be easily modified to tolerate random persistent classification noise in MQs. [ABSTRACT FROM AUTHOR]