All reports by Author Stephan Waack:

__
TR01-073
| 24th October 2001
__

Beate Bollig, Philipp Woelfel, Stephan Waack#### Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Revisions: 1

__
TR96-017
| 19th February 1996
__

Christoph Meinel, Stephan Waack#### The ``Log Rank'' Conjecture for Modular Communication Complexity

__
TR95-034
| 30th June 1995
__

Christoph Meinel, Stephan Waack#### Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems

__
TR94-022
| 12th December 1994
__

Christoph Meinel, Stephan Waack#### The MÃ¶bius Function, Variations Ranks, and Theta(n)--Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem

Beate Bollig, Philipp Woelfel, Stephan Waack

Branching programs are a well-established computation model

for Boolean functions, especially read-once branching programs

have been studied intensively. Exponential lower bounds for

deterministic and nondeterministic read-once branching programs

are known for a long time. On the other hand, the problem of

proving superpolynomial lower bounds ...
more >>>

Christoph Meinel, Stephan Waack

The ``log rank'' conjecture consists in the question how exact

the deterministic communication complexity of a problem can be

determinied in terms of algebraic invarants of the communication

matrix of this problem. In the following, we answer this question

in the context of modular communication complexity. ...
more >>>

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 >>>

Christoph Meinel, Stephan Waack

We prove that the modular communication complexity of the

undirected graph connectivity problem UCONN equals Theta(n),

in contrast to the well-known Theta(n*log n) bound in the

deterministic case, and to the Omega(n*loglog n) lower bound

in the nondeterministic case, recently proved by ...
more >>>