Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PARALLEL TIME COMPLEXITY:
Reports tagged with parallel time complexity:
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 >>>




ISSN 1433-8092 | Imprint