Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PARALLEL RANDOM-ACCESS MACHINE:
Reports tagged with parallel random-access machine:
TR95-004 | 1st January 1995
Martin Dietzfelbinger, Miroslaw Kutylowski, RĂ¼diger Reischuk

Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs


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


TR96-052 | 2nd October 1996
Martin Dietzfelbinger

Gossiping and Broadcasting versus Computing Functions in Networks

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




ISSN 1433-8092 | Imprint