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