Broder@SU-SCORE.ARPA@SU-Score@sri-unix.UUCP (09/30/83)
From: Andrei Broder <Broder@SU-SCORE.ARPA@SU-Score>
[Reprinted from the SU-SCORE bboard.]
The "Algorithms for Lunch Bunch" (AFLB) is a weekly seminar in
analysis of algorithms held by the Stanford Computer Science
Department, every Thursday, at 12:30 p.m., in Margaret Jacks Hall, rm.
352.
At the first meeting this year, (Thursday, October 6) Prof. Jeffrey D.
Ullman, from Stanford, will talk on "A time-communication tradeoff"
Abstract follows.
Further information about the AFLB schedule is in the file
[SCORE]<broder>aflb.bboard .
If you want to get abstracts of the future talks, please send me a
message to put you on the AFLB mailing list. If you just want to know
the title of the next talk and the name of the speaker look at the
weekly Stanford CSD schedule that is (or should be) sent to every
bboard.
------------------------
10/6/83 - Prof. Jeffrey D. Ullman (Stanford):
"A time-communication tradeoff"
We examine how multiple processors could share the computation of a
collection of values whose dependencies are in the fom of a grid,
e.g., the estimation of nth derivatives. Two figures of merit are the
time t the shared computation takes and the amount of communication c,
i.e., the number of values that are either inputs or are computed by
one processor and used by another. We prove that no matter how we
share the responsibility for computing an n by n grid, the law ct =
OMEGA(n^3) must hold.
******** Time and place: Oct. 6, 12:30 pm in MJ352 (Bldg. 460) *******