On Lower Bounds for Parity Branching Programs (2009)
Matthias Homeister, Referent Prof, Dr. St. Waack, Korreferent Pd, Dr. Carsten Damm, ...
I would like to acknowledge all the people whose support gave me the possibility to undergo the work of this thesis. First of all, I would like to express my thanks to my Advisor Prof. Dr. Stephan...
On approximation by ⊕OBDDs (2008)
Henrik Brosenne, Carsten Damm, Matthias Homeister, Stephan Waack
The usual OBDD-data structure can easily be equipped with nondeterminism by allowing several edges with the same label leaving a node. Depending on how acceptance is defined we distinguish between...
Deterministic 0L Languages are of Very Low Complexity: D0L is in AC 0 (2007)
Carsten Damm, Markus Holzer, Klaus-Jörn Lange, Peter Rossmanith
Languages dened by iterated homomorphisms, i.e., D0L systems, are closely related to the arithmetic of small numbers. Based on this interrelation we improve the upper bound NC 1 on the complexity of...
On the Complexity of Tensor Formulae (2007)
We consider formulae on base of sum, product, and tensor product of matrices . In particular, we consider matrices over the Boolean semi-ring B = (f0; 1g; _; ^) and over the two-element eld F 2 =...
Deterministic 0L Languages are of Very Low Complexity: D0L is in AC 0 (2007)
Carsten Damm, Markus Holzer, Klaus-Jörn Lange, Peter Rossmanith
Languages defined by iterated homomorphisms, i.e., D0L systems, are closely related to the arithmetic of small numbers. Based on this interrelation we improve the upper bound NC 1 on the complexity...
On the Complexity of Some Arithmetic Problems over IF2[T] (2007)
Eric Allender, Anna Bernasconi, Carsten Damm, Michael Saks, Igor Shparlinski
In this paper, we study various combinatorial complexity characteristics of Boolean functions related to some natural arithmetic problems about polynomials over IF2. In particular, we consider the...
Expressing Uniformity via Oracles (2007)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Carsten Damm, Carsten Damm, Markus Holzer, ...
'MAIL ME CLEAR', body 'TechReports.HowTo ' followed by an empty line, for detailed instructions
Score-based prediction of genomic islands in prokaryotic genomes using hidden Markov models (2006)
Waack, Stephan, Keller, Oliver, Asper, Roman, Brodag, Thomas, Damm, Carsten, Fricke, Wolfgang, ...
Abstract Background Horizontal gene transfer (HGT) is considered a strong evolutionary force shaping the content of microbial genomes in a substantial manner. It is the difference in speed enabling...
Score-based prediction of genomic islands in prokaryotic genomes using hidden Markov models (2006)
Waack, Stephan, Keller, Oliver, Asper, Roman, Brodag, Thomas, Damm, Carsten, Fricke, Wolfgang Florian, ...
Background: Horizontal gene transfer (HGT) is considered a strong evolutionary force shaping the content of microbial genomes in a substantial manner. It is the difference in speed enabling the rapid...
Göttingen, Univ., Diss., 2003.
The Complexity of Tensor Calculus (2000)
Carsten Damm, Markus Holzer, Pierre Mckenzie
Tensor calculus over semirings is shown relevant to complexity theory in unexpected ways. First, evaluating well-formed tensor formulas with explicit tensor entries is shown complete for \PhiP, for...
On the Complexity of Tensor Formulae (1999)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Carsten Damm, Carsten Damm
We consider formulae on base of sum, product, and tensor product of matrices . In particular, we consider matrices over the Boolean semi-ring B = (f0; 1g; _; ^) and over the two-element eld F 2 =...
On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols (1998)
Mathematik Informatik, Trierer Forschungsberichte, Trierer Forschungsberichte, Fachbereich Iv, Fachbereich Iv, Carsten Damm, ...
We compare two computational models that appeared in the literature in a Boolean setting and in an analog setting based on modular arithmetic. We prove that in both cases the arithmetic version can...
On Alternating vs. Parity Communication Complexity (1998)
Mathematik Informatik, Trierer Forschungsberichte, Trierer Forschungsberichte, Fachbereich Iv, Fachbereich Iv, Carsten Damm, ...
We prove that for any O(1)-alternating communication protocol of length L computing a function f and for 0 ! ffi there is a parity communication protocol of length O((L \Gamma log ffi ) O(1) )...
Expressing Uniformity via Oracles (1997)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Carsten Damm, Carsten Damm, Markus Holzer, ...
s and 1/TechReports/FullText Via WWW: URL http://www.informatik.uni-trier.de/Reports/List Via email: Send a mail to ftpmail@ftp.informatik.uni-trier.de, subject 'MAIL ME CLEAR', body...
Expressing Uniformity via Oracles (1997)
Carsten Damm, Markus Holzer, Peter Rossmanith, Fakultat Fur Informatik
We study under what circumstances different uniformity notions for NC 1 lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access...
Expressing Uniformity via Oracles (1997)
Carsten Damm, Markus Holzer, Peter Rossmanith
We study under what circumstances different uniformity notions for NC 1 lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access...
Expressing Uniformity via Oracles (1997)
Carsten Damm, Markus Holzer, Peter Rossmanith
We study under what circumstances different uniformity notions for Boolean circuits of logarithmic depth lead to the same complexity class. Our investigations are based on a characterization of...
A note on Spectral Lower Bound Arguments for Decision Trees (1997)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Carsten Damm, Carsten Damm
Let DT(f) and depth(f) be the minimal size and the minimal average depth of decision trees that compute a given Boolean function f : f0; 1g n ! f+1; \Gamma1g. Based on geometric arguments we give a...
Some Bounds on Multiparty Communication Complexity of Pointer Jumping (1996)
Carsten Damm, Stasys Jukna, Jirí Sgall
We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping. The pointer jumping function takes as its input a directed...
Some Bounds on Multiparty Communication Complexity of Pointer Jumping (1996)
Carsten Damm, Stasys Jukna, Jirí Sgall
. We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping. The pointer jumping function takes as its input a...
Some Bounds On Multiparty Communication Complexity Of Pointer Jumping (1996)
. We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping. The pointer jumping function takes as its input a...
Inductive Counting For Width-Restricted Branching Programs (1996)
Markus Holzer, Carsten Damm, Carsten Damm, Fachbereich Iv Informatik
. As an application of the inductive counting technique to a circuit-like model, we prove that complementation on nondeterministic branching programs can be done without increasing the width too...
Some Bounds on Multiparty Communication Complexity of Pointer Jumping (1995)
Mathematik Informatik, Trierer Forschungsberichte, Jirí Sgall, Fachbereich Iv, Carsten Damm, Carsten Damm, ...
We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping. The pointer jumping function takes as its input a directed...
Automata That Take Advice (1995)
Fachbereich Iv-informatik, Fakultat Fur Informatik, Carsten Damm, Carsten Damm, Carsten Damm, Markus Holzer, ...
Karp and Lipton introduced advice-taking Turing machines to capture nonuniform complexity classes. We study this concept for automata-like models and compare it to other nonuniform models studied in...
Automata That Take Advice (1995)
. Karp and Lipton introduced advice-taking Turing machines to capture nonuniform complexity classes. We study this concept for automata-like models and compare it to other nonuniform models studied...
On Multiparty Games for Pointer Jumping (1995)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Carsten Damm, Carsten Damm, Stasys Jukna, ...
We consider the multiparty communication complexity of the pointer jumping function Jump n k : Our main results are matching upper and lower bounds of order \Theta i n log (k\Gamma1) n j for the...
Inductive Counting below LOGSPACE (1994)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Carsten Damm, Markus Holzer, ...
We apply inductive counting to nondeterministic branching programs and prove that complementation on this model can be done without increasing the width of the branching programs too much. This shows...
Inductive Counting below LOGSPACE (1994)
. We apply the inductive counting technique to nondeterministic branching programs and prove that complementation on this model can be done without increasing the width of the branching programs too...
Inductive Counting below LOGSPACE (1994)
Trierer Forschungsberichte, Fachbereich Iv, Mathematik Informatik, Mathematik Informatik, Carsten Damm, Carsten Damm, ...
s and 1/TechReports/FullText Via WWW: URL http://www.informatik.uni-trier.de/Reports/List Via email: Send a mail to ftpmail@ftp.informatik.uni-trier.de, subject 'MAIL ME CLEAR', body...
How much ExOR improves on OR? (1993)
Mathematik Informatik, Trierer Forschungsberichte, Trierer Forschungsberichte, Fachbereich Iv, Fachbereich Iv, Carsten Damm, ...
Very recently the Beßlich-Sasao-conjecture has been proved: ExOR-sumof -products (ESOP's) need at most as many products as ordinary sum-ofproducts (SOP's) to realize symmetric Boolean...
Symmetric Functions in AC 0 [2] (1993)
Mathematik Informatik, Trierer Forschungsberichte, Trierer Forschungsberichte, Fachbereich Iv, Fachbereich Iv, Carsten Damm, ...
We consider symmetric Boolean functions computable by polynomial size constant depth circuits with AND-, OR-, and PARITY-gates. If the depth is restricted to 2 or if PARITY-gates are disallowed...
Parallel Complexity of Iterated Morphisms and the Arithmetic of Small Numbers (1992)
Carsten Damm, Markus Holzer, Klaus-Jörn Lange
We improve several upper bounds to the complexity of the membership problem for languages defined by iterated morphisms (D0L systems). The complexity bounds are expressed in terms of DLOGT IME...
Structure and Importance of Logspace-MOD-Classes (1992)
Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel
. We refine the techniques of Beigel, Gill, Hertrampf [4] who investigated polynomial time counting classes, in order to make them applicable to the case of logarithmic space. We define the...
Berlin, Humboldt-Univ., Diss., 1991 (Nicht für den Austausch).
Score-based prediction of genomic islands in prokaryotic genomes using hidden Markov models
Waack, Stephan, Keller, Oliver, Asper, Roman, Brodag, Thomas, Damm, Carsten, Fricke, Wolfgang Florian, ...
Score-based prediction of genomic islands in prokaryotic genomes using hidden Markov models
Waack, Stephan, Keller, Oliver, Asper, Roman, Brodag, Thomas, Damm, Carsten, Fricke, Wolfgang Florian, ...
On Relations Between Counting Communication Complexity Classes
Carsten Damm Fb, Carsten Damm, Matthias Krause, Lehrstuhl Informatik Ii, Christoph Meinel, ...
We 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...
On Relations Between Counting Communication Complexity Classes
Carsten Damm, Matthias Krause, Seminargebaude A, Christoph Meinel, ...
We 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...