ColloquiaChange in Date: Shah/Dissertation Defense/Now 5-31-01

[Margaret Jaffey]

The day and time of Mr. Pradyut Shah's dissertation defense have been changed.

It will be held on Thursday, May 31st at 2:00 p.m. (instead of 
Friday, June 1st at 2:30 p.m.).  The location (Ry 251) remains the 
same.  Please make a note of the change.


This is a revised announcement of Mr. Pradyut Shah's dissertation defense.


Date:	Thursday, May 31, 2001

Time:	2:00 p.m.

Place:	Ryerson 251

Candidate:	  Pradyut Shah

Title:	Lower Bounds for Parallel Algorithms

Abstract:

  Proving the optimality of algorithms for important combinatorial
   problems and determining their intrinsic hardness properties
   requires finding good lower bounds for them.

   The model of computation we consider is the PRAM without bit
   operations. The model eliminates those operations that allow
   bit-extraction or updates of the bits of the individual registers,
   but provides the usual arithmetic, indirect referencing, conditional
   and unconditional branch operations at unit cost. We consider here
   an unbounded fan-in model, in which the operations $\{+, \min,
   \max\}$ can have unbounded fan-in at unit cost.

   We show that computing the shortest path between two specified
   vertices in a weighted graph on $n$ vertices cannot be solved in
   $o(\log n)$ time on an unbounded fan-in PRAM without bit operations
   using $\poly(n)$ processors, even when the bit-lengths of the
   weights on the edges are restricted to be of size $O(\log^3 n)$.
   This shows that the matrix-based repeated-squaring algorithm for the
   Shortest Path problem is optimal in the unbounded fan-in PRAM model
   without bit operations.

   We also show that computing the maximum blocking flow (or
   equivalently the maximum flow in a directed acyclic graph) cannot be
   computed in time $o(n^{1/8})$ with polynomially many processors in
   the same model, even when the inputs are restricted to be of length
   $O(n^2)$.

   The above lower bounds (with slightly weaker parameters) also apply
   in the case of randomized algorithms where the algorithm is allowed
   to flip coins.

   The thesis also provides lower bounds for other restricted cases of
   these problems which are useful in practice. We also obtain as a
   corollary a weak lower bound on the problem of computing weighted
   matchings in graphs which is not known to have a fast parallel
   algorithm.

Candidate's Advisor:  Prof. Ketan Mulmuley

A copy of Mr. Shah's dissertation will be available in Ry 161A.

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey			margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=