All reports by Author Christoph Meinel:

__
TR98-039
| 14th July 1998
__

Christoph Meinel, Thorsten Theobald#### Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey

__
TR96-017
| 19th February 1996
__

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

__
TR96-010
| 9th February 1996
__

Christoph Meinel, Anna Slobodova#### An Adequate Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams

Revisions: 1

__
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

Christoph Meinel, Thorsten Theobald

Many problems in computer-aided design of highly integrated circuits

(CAD for VLSI) can be transformed to the task of manipulating objects

over finite domains. The efficiency of these operations depends

substantially on the chosen data structures. In the last years,

ordered binary decision diagrams (OBDDs) have ...
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, Anna Slobodova

Reducibility concepts are fundamental in complexity theory.

Usually, they are defined as follows: A problem P is reducible

to a problem S if P can be computed using a program or device

for S as a subroutine. However, in the case of such restricted

models as ...
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 >>>