Claudia Bertram, Thomas Hofmeister

We consider the threshold circuit complexity of computing

the multiple product modulo m in threshold circuits.

Christoph Meinel, Stephan Waack

We investigate the probabilistic communication complexity

(more exactly, the majority communication complexity,)

of the graph accessibility problem GAP and

its counting versions MOD_k-GAP, k > 1.

Due to arguments concerning matrix variation ranks

and certain projection reductions, we prove

that, for any partition of the input variables,

more >>>

Helmut Veith

In this paper, we present stronger results in the theory of succinct

problem representation by boolean circuits, and establish a close

relationship between succinct problems and leaf languages. As

a major tool, we use quantifierfree projection reductions

from descriptive complexity theory.

In particular, we show that the succinct upgrading ... more >>>