All reports by Author Martin Dietzfelbinger:

__
TR96-063
| 6th November 1996
__

Martin Dietzfelbinger#### The Linear-Array Problem in Communication Complexity Resolved

__
TR96-052
| 2nd October 1996
__

Martin Dietzfelbinger#### Gossiping and Broadcasting versus Computing Functions in Networks

__
TR95-004
| 1st January 1995
__

Martin Dietzfelbinger, Miroslaw Kutylowski, RĂ¼diger Reischuk#### Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs

Martin Dietzfelbinger

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k,

connected by k links to form a linear array, compute a function f(x,y), for

inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and

y is only known to P_k; the intermediate ...
more >>>

Martin Dietzfelbinger

The fundamental assumption in the classical theory of

dissemination of information in interconnection networks

(gossiping and broadcasting) is that atomic pieces of information

are communicated. We show that, under suitable assumptions about

the way processors may communicate, computing an n-ary function

that has a "critical input" (e.g., ...
more >>>

Martin Dietzfelbinger, Miroslaw Kutylowski, RĂ¼diger Reischuk

It was shown some years ago that the computation time for many important

Boolean functions of n arguments on concurrent-read exclusive-write

parallel random-access machines

(CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n.

On the other hand, it ...
more >>>