victor@WATSON.IBM.COM (04/12/91)
Here is detailed information about WOBCATS on Friday, April 19 to be held in
Seattle at the University of Washington.
It is scheduled for Balmer Hall Room 413.
For a half hour prior to the first talk there will be coffee, tea and sweet
starchy stuff nearby in Balmer Hall Room 411.
The schedule is as follows:
11:00 - 11:30 Coffee and Tea (Balmer 411)
11:30 - 12:30 'A Faster Deterministic Max-Flow Algorithm'
Valerie King, NEC Research Institute
I will present a deterministic max flow algorithm which runs
in time O(min{mn + n^{2 + c},mnlogn}), for any constant c.
This improves upon Alon's 1989 bound of
O(min {mn + n^{8/3}logn, mnlogn}) and gives an O(mn)
deterministic
algorithm for all m > n^{1 + c}. Thus it extends the range of
m/n for which an O(mn) algorithm is known, and matches the 1988
O(mnlog (n^2/m)) algorithm of Goldberg and Tarjan for smaller
values of m/n.
Our algorithm is essentially a derandomized version of the 1989
Cheriyan-Hagerup randomized algorithm whose running time is
O(min {mn + n^2 (logn)^2}, mnlogn}). Cheriyan and Hagerup reduce
the problem of solving max flow to finding a strategy in a
certain
two person combinatorial game where the payoff reflects the cost
of the computation. Randomization is used to choose a successful
strategy. In 1989, Alon found the fastest deterministic
algorithm
for max flow, by derandomizing their strategy, but at a cost of a
factor of n^{2/3} /logn in the payoff. By slightly modifying the
rules of the game, we are able to find a deterministic strategy
which improves the bound to within an n^c factor of the
randomized
version.
(This is joint work with S. Rao and R. Tarjan.)
12:30 - 2:00 Lunch Break
2:00 - 3:00 'Probabilistic Algorithms for Nearly Constant-Time Parallel
Computation'
Yossi Gil, University of British Columbia
This talk presents extremely fast randomized algorithms for
several fundamental problems in parallel computation.
The algorithms for the problems below run in (log* n)^O(1)
(``nearly-constant'') expected time, and optimal speedup.
Problems include:
- Supporting dictionary (i.e., insert, delete, lookup)
operations
this is the first optimal dictionary algorithm that is in RNC.
- Load balancing; this is a fundamental tool in parallel
computation
- Simulation of MAXIMUM (a powerful CRCW model) PRAM on
COLLISION (a weak CRCW model) PRAM.
- Integer chain-sorting.
Algorithms are based on a general log* n probabilistic
design paradigm.
As building blocks, we present several techniques for estimating
the size of a set in constant time, or nearly-constant time, in
various settings. These algorithms are of independent interest.
3:00 - 3:15 Break and hot gossip exchange
3:15 - 4:15 'Lower Bounds on Universal Traversal Sequences for Cycles and
Higher Degree Graphs'
Martin Tompa, University of Washington
A "universal traversal sequence" is a string U over
{0,1,...,d-1}
such that, for any d-regular, n-vertex, connected, labeled graph
G and any vertex s of G, a traversal of G according to U
starting
at s visits every vertex of G. This talk will motivate the study
of universal traversal sequences, and present new lower bounds.
In particular, universal traversal sequences for cycles require
length proportional to n**1.29, improving the previous bound of
nlog n. For d at least 3, universal traversal sequences for
d-regular graphs require length proportional to
(d**0.71)(n**2.29). For constant d, this improves the previous
bound of (n**2) log n.
Balmer Hall is a bulding nearly as ugly as Computer Science's own Sieg Hall
and is located near the entrance to the university off N.E. 45th St. and
17th Ave. N.E.
Parking tags will be available at the kiosk at this entrance. Please identify
yourself as being from WOBCATS. There is a parking lot just to your right as
you enter which will be where you will likely be told to park. Balmer Hall
is not far to the left of the main entrance. You can get directions at the
kiosk.
To get to the university take I-5 to the N.E. 45th street exit and go east to
17th Avenue (at the top of the hill) and turn right at the lights.
If you are intending to stay over night in Seattle we will try to make
arrangements for a place to stay.
Paul