Zvi Galil
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Zvi Galil has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Pavol Duris2 shared publications
A. M. Ben-Amram
Computer Science, Tel-Aviv Academic College, 4 Antokolski Str., 64044 Tel-Aviv, Israel.
1 shared publication
Latest Publications
- 1 May 2001
- Published by Springer Nature in Algorithmica
- Vol. 30 (1) , 34-66
A Generalization of a Lower Bound Technique due to Fredman and Saks
- 1 May 2001
- Published by Springer Nature in Algorithmica
- Vol. 30 (1) , 34-66
A Generalization of a Lower Bound Technique due to Fredman and Saks
- 1 October 1987
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 326-330
Two lower bounds in asynchronous distributed computation
We introduce new techniques for deriving lower bounds on the message complexity in asynchronous distributed computation. These techniques combine the choice of specific patterns of communication delays and crossing sequence arguments with consideration of the speed of propagation of messages, together with careful counting of messages in different parts of the network. They enable us to prove the following results, settling two open problems: An Ω(n log* n) lower bound for the number of messages sent by an asynchronous algorithm for computing any nonconstant function on a bidirectional ring of n anonymous processors. An Ω(n log n) lower bound for the average number of messages sent by any maximum finding algorithm on a ring of n processors, in case n is known.
- 1 October 1987
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 326-330
Two lower bounds in asynchronous distributed computation
We introduce new techniques for deriving lower bounds on the message complexity in asynchronous distributed computation. These techniques combine the choice of specific patterns of communication delays and crossing sequence arguments with consideration of the speed of propagation of messages, together with careful counting of messages in different parts of the network. They enable us to prove the following results, settling two open problems: An Ω(n log* n) lower bound for the number of messages sent by an asynchronous algorithm for computing any nonconstant function on a bidirectional ring of n anonymous processors. An Ω(n log n) lower bound for the average number of messages sent by any maximum finding algorithm on a ring of n processors, in case n is known.
- 1 October 1981
- Published by Institute of Electrical and Electronics Engineers (IEEE)
A time-space tradeoff for language recongnition
We define a language L and show that its time and space complexities T and S must satisfy T2S ≥ cn3 even allowing machines with multiple (non random) access to the input.
- 1 October 1981
- Published by Institute of Electrical and Electronics Engineers (IEEE)
A time-space tradeoff for language recongnition
We define a language L and show that its time and space complexities T and S must satisfy T2S ≥ cn3 even allowing machines with multiple (non random) access to the input.