Author name cluster

R. Fleischer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

I&C Journal 1995 Journal Article

A Communication-Randomness Tradeoff for Two-Processor Systems

R. Fleischer
H. Jung
K. Mehlhorn

We present a tight tradeoff between the expected communication complexity C (for a two-processor system) and the number R of random bits used by any Las Vegas protocol for the list-nondisjointness function of two lists of n numbers of n bits each. This function evaluates to 1 if and only if the two lists correspond in at least one position. We show a log(n 2/ C ) lower bound on the number of random bits used by any Las Vegas protocol, Ω(n) ≤ C ≤ O(n 2). We also show that expected communication complexity C, Ω(n log n) ≤ C ≤ O(n 2), can be achieved using no more than log(n 2/ C ) + ⌈log(2 + log(n 2/ C ))⌉ + 6 random bits.

Details DOI

I&C Journal 1993 Journal Article

A Lower Bound for the Worst Case of Bottom-Up-Heapsort

R. Fleischer
B.P. Sinha
C. Uhrig

Bottom-Up-Heapsort is a variant of Heapsort. Until now, its worst case complexity for the number of comparisons has been known to be bounded above by 1. 5n log n + 0(n), where n is the number of elements to be sorted; but it was conjectured to be n log n + o(n log n). In this paper we give a construction that proves an asymptotic lower bound of 1. 25n log n − 0(n log log n) comparisons for the worst case.

Details DOI