1,720,987 research outputs found
On the Descriptive and Algorithmic Power of Parity Ordered Binary Decision Diagrams
No full textAbstractThe main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a parity OBDD (ordered binary decision diagram). Moreover, we prove that the synthesis and the equivalence test for ⊕OBDDs, which are the fundamental operations for circuit verification, have polynomial time deterministic solutions. We conclude that it takes deterministic polynomial time to decide whether the parity of clauses/implicants is satisfiable. Several functions typically used as examples in theory, e.g., the indirect storage access function, have exponential OBDD-size but are of polynomial size if ⊕OBDDs are used
The "log rank" conjecture for modular communication complexity
No full textThe "log rank" conjecture involves the question of how precisely the deterministic communication complexity of a problem can be described in terms of algebraic invariants of the communication matrix of this problem. We answer this question in the context of modular communication complexity. We show that the modular communication complexity can be exactly characterised in terms of the logarithm of a certain rigidity function of the communication matrix. Thus, we are able to exactly determine the modular communication complexity of several problems, such as, e.g., set disjointness, comparability, and undirected graph connectivity. From the bounds obtained for the modular communication complexity we deduce exponential lower bounds on the size of depth-two circuits having arbitrary symmetric gates at the bottom level and a MODm-gate at the top
Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
No full textOrdered binary decision diagrams with repeated tests are considered both in complexity theory and in applications. Bollig et al. have proved in [B. Bollig, M. Sauerhoff, D. Sieling, I. Wegener, Hierarchy theorems of kOBDDs and kIBDDs, Theoret. Comput. Sci. 205 (1998) 45-60] a tight hierarchy result for the classes of functions representable by k layers of polynomial-size deterministic ordered binary decision diagrams. In this paper the nondeterministic case is investigated, where the layers are driven by one and the same variable ordering. For k being a constant, it is shown that for the existential, the parity-, and the majority acceptance mode the analogous hierarchy collapses. (c) 2005 Elsevier B.V. All rights reserved
AUGUSTUS: a web server for gene finding in eukaryotes
No full textWe present a www server for AUGUSTUS, a novel software program for ab initio gene prediction in eukaryotic genomic sequences. Our method is based on a generalized Hidden Markov Model with a new method for modeling the intron length distribution. This method allows approximation of the true intron length distribution more accurately than do existing programs. For genomic sequence data from human and Drosophila melanogaster, the accuracy of AUGUSTUS is superior to existing gene-finding approaches. The advantage of our program becomes apparent especially for larger input sequences containing more than one gene. The server is available at http://augustus.gobics.de
Graph-driven free parity BDDs: Algorithms and lower bounds
No full textWe investigate graph-driven free paxity BDDs, which strictly generalize the two well-known models parity OBDDs and graph-driven free BDDs. The first main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph-driven free parity BDD. The second main result is an exponential lower bound on the size of graph-driven free parity BDD for linear code functions
Lower bounds for general graph-driven read-once parity branching programs
No full textWe prove the first exponential lower bounds on the size of graph-driven read-once parity branching programs. The functions used are linear codes, permutation matrices and a function that has small unrestricted read-once parity branching programs. Moreover, we characterize all BP1s that are guided by graph orderings. The latter is the case if and only if for each input there is a variable ordering that is compatible with each computation path for the input
Lower bounds for general graph-driven read-once parity branching programs
No full textWe prove the first exponential lower bounds on the size of graph-driven read-once parity branching programs. The functions used are linear codes, permutation matrices and a function that has small unrestricted read-once parity branching programs. Moreover, we characterize all BP1s that are guided by graph orderings. The latter is the case if and only if for each input there is a variable ordering that is compatible with each computation path for the input
Graph-driven free parity BDDs: Algorithms and lower bounds
No full textWe investigate graph-driven free paxity BDDs, which strictly generalize the two well-known models parity OBDDs and graph-driven free BDDs. The first main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph-driven free parity BDD. The second main result is an exponential lower bound on the size of graph-driven free parity BDD for linear code functions
On relations between counting communication complexity classes
No full textAbstractWe develop upper and lower bound arguments for counting acceptance modes of communication protocols. A number of separation results for counting communication complexity classes is established. This extends the investigation of the complexity of communication between two processors in terms of complexity classes initiated by Babai et al. (Proceedings of the 27th IEEE FOCS, 1986, pp. 337–347) and continued in several papers (e.g., J. Comput. System Sci. 41 (1990) 402; 49 (1994) 247; Proceedings of the 36th IEEE FOCS, 1995, pp. 6–15).In particular, it will be shown that for all pairs of distinct primes p and q the communication complexity classes MODpPcc and MODqPcc are incomparable with regard to inclusion. The same is true for PPccand MODmPcc, for any number m⩾2. Moreover, non-determinism and modularity are incomparable to a large extend. On the other hand, if m=p1ℓ1·…·prℓr is the prime decomposition of m⩾2, then the complexity classes MODmPcc and MODρ(m)Pcc coincide, where ρ(m)=p1·…·pr.The results are obtained by characterizing the modular and probabilistic communication complexity in terms of the minimum rank of matrices ranging over certain equivalence classes. Methods from algebra and analytic geometry are used.This paper is the completely revised and strongly extended version of the conference paper Damm et al. (Proc. 9th Ann. STACS, pp. 281–291) where a subset of the results was presented
Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
No full textWe investigate well-structured graph-driven parity-FBDDs, which strictly generalize
the two well-known models parity OBDDs and well-structured graph-driven FBDDs.
The first main result is a characterization of the complexity of Boolean
functions represented by well-structured graph-driven parity-FBDDs in terms of
invariants of the function represented and the graph-ordering used.
As a consequence, we derive a lower bound criterion and prove an exponential
lower bound for certain linear code functions.
The second main result of this paper is a polynomial time algorithm that
minimizes the number of nodes in a graph-driven parity-FBDD
- …
