Arrow Research search

Author name cluster

H. Jung

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.

3 papers
2 author rows

Possible papers

3

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

Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of Directed Acyclic Graphs with Communication Delays

  • H. Jung
  • L.M. Kirousis
  • P. Spirakis

We present here an n τ+1 algorithm for optimally scheduling a dag of n nodes on a multiprocessor when the message-to-instruction ratio parameter is τ. Our algorithm constructs an optimum schedule which uses at most n processors. We furthermore show lower bound results on the amount of recomputation needed, thus answering an open question posed by Papadimitriou and Yannakakis. In addition, precise lower bounds are demonstrated for the scheduling time of full binary trees. Our techniques may contribute to an important new understanding of parallel scheduling when the message delay is significant, which is usually the case.

Details DOI
v2026.09.13