Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR96-017 | 19th February 1996
Christoph Meinel, Stephan Waack

The ``Log Rank'' Conjecture for Modular Communication Complexity

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

TR95-034 | 30th June 1995
Christoph Meinel, Stephan Waack

Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems

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

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

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

ISSN 1433-8092 | Imprint