Carsten Damm

I&C Journal 2001 Journal Article

Circuit and Decision Tree Complexity of Some Number Theoretic Problems

• Anna Bernasconi
• Carsten Damm
• Igor Shparlinski

We extend the area of applications of the Abstract Harmonic Analysis to lower bounds on the circuit and decision tree complexity of Boolean functions related to some number theoretic problems. In particular, we prove that deciding if a given integer is square-free and testing co-primality of two integers by unbounded fan-in circuits of bounded depth requires superpolynomial size.

MFCS Conference 1998 Conference Paper

On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols

• Carsten Damm

Abstract 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 to some extend simulate the Boolean version. Although the models are very different, the proofs rely on the same idea based on the Schwartz-Zippel-Theorem. In the first part we prove that depth d semi-unbounded Boolean circuits can be simulated by depth 2 d + O (log d + log n ) semi-unbounded arithmetic circuits, regardless of the size. This is an improvement on a similar construction in [3] that achieves depth 3 d + O (log s + log n ), where s is the size of the original circuit. Our construction is simpler and uses fewer random bits. In the second part we prove, that two-party parity communication protocols can approximate nondeterministic communication protocols. A strict simulation of one by the other is impossible as was shown in [2].

I&C Journal 1996 Journal Article

Inductive Counting for Width-Restricted Branching Programs

• Carsten Damm
• Markus Holzer

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 excessively. A consequence of this result is that the class of languages recognized by a generalization of nonuniform finite automata to nonconstant space is closed under complement.

MFCS Conference 1995 Conference Paper

Automata That Take Advice

• Carsten Damm
• Markus Holzer 0001

Abstract 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 connection with formal languages in the literature. Based on this we obtain complete separations of the classes of the Chomsky hierarchy relative to advices.

MFCS Conference 1994 Conference Paper

Inductive Counting Below LOGSPACE

• Carsten Damm
• Markus Holzer 0001

Abstract 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 much. This shows that for an arbitrary space bound s(n), the class of languages accepted by nonuniform nondeterministic O(s(n)) space bounded Turing machines is closed under complementation. As a consequence we obtain for arbitrary space bounds s(n) that the alternation hierarchy of nonuniform O(s(n)) space bounded Turing machines collapses to its first level. This improves the previously known result of Immerman [6] and Szelepcsényi [12] to space bounds of order o (log n ) in the nonuniform setting. This reveals a strong difference to the relations between the corresponding uniform complexity classes, since very recently it has been proved that in the uniform case the alternating space hierarchy does not collapse for sublogarithmic space bounds [3, 5, 9].

MFCS Conference 1992 Conference Paper

Parallel Complexity of Iterated Morphisms and the Arithmetic of Small Numbers

• Carsten Damm
• Markus Holzer 0001
• Klaus-Jörn Lange

Abstract 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 DLOGTIME -uniform circuit families. We prove: 1) For polynomially growing DOL systems the membership problem is contained in AC 0. 2) For arbitrary DOL systems the membership problem is contained in NC 1. 3) The latter can be improved to TC 0 if and only if upper bounds to a number of natural arithmetic problems can be improved to TC 0. 4) The general D0L membership problem (the D0L system is part of the input) is contained in Cook's class DET.

TCS Journal 1992 Journal Article

Separating complexity classes related to Ω-decision trees

• Carsten Damm
• Christoph Meinel

By proving exponential lower and polynomial upper bounds for parity decision trees and collecting similar bounds for nondeterministic and co-nondeterministic decision trees, the complexity classes related to polynomial-size deterministic, nondeterministic, co-nondeterministic, parity, and alternating decision trees are completely separated. Considering alternating decision trees, it is shown that the number of alternations between, say, ⋎-nodes and ⋏-nodes strongly influences their computational power.

MFCS Conference 1990 Conference Paper

The Complexity of Symmetric Functions in Parity Normal Forms

• Carsten Damm