clarke@utcsri.UUCP (Jim Clarke) (02/12/86)
(GB = Galbraith Building, 35 St. George Street)
(SF = Sandford Fleming Building, 10 King's College Rd.)
THEORY SEMINAR, Tuesday, Feb. 18, 11 am, SF1105
Professor Umesh Vazirani
Mathematical Sciences Research Institute
"Matching is as Easy as Matrix Inversion"
Abstract: Whereas in the case of sequential computation the complex-
ity of a search problem is closely related to the complexity of its associ-
ated decision problem via self-reducibility, this does not appear to be the
case for parallel computation. A case in point is the maximum matching
problem in graphs. A fast parallel algorithm for the decision problem
`Given a graph, does it have a perfect matching?' preceeded by several
years the RNC3 algorithm of Karp, Upfal & Wigderson for the search problem
`Given a graph having a perfect matching, find one such matching'. We
relate the parallel complexity of an arbitrary search problem to that of
the weighted version of the decision problem. In the case of the matching
problem this yields a simple RNC2 algorithm for constructing a perfect
matching in a graph. A striking feature of the algorithm is that its only
computationally non-trivial step is a single inversion of an nxn integer
matrix.
ARTIFICIAL INTELLIGENCE SEMINAR, Tues. Feb.18, 3 pm, SF1105
Joshua Zeevi
Technion - Israel Institute of Tech.
"Image Representation in Vision:
The Generalized Gabor Scheme"
Abstract: Extensive processing and reorganization of information
is accomplished in vision as signals flow centrally. The rate of informa-
tion flow is reduced by position-dependent (inhomogeneous) sampling. This
principle of nonuniform processing is further elaborated at the cortical
level where images are decomposed into a finite set of Gabor elementary
functions. The basic features and advantages of visual information pro-
cessing in a combined frequency-position space will be discussed with spe-
cial emphasis on trade-offs in spatial and frequency sampling rates, phase
quantization and image representation by partial localized (Gabor) informa-
tion.
SYSTEMS SEMINAR, Thursday, Feb.20, 11 am, GB 220
Professor R. Vasudevan
University of Calgary
"Interkernel Layer"
Abstract: The interkernel layer is a lightweight transport layer
that provides reliable and efficient transportation of data between
machines in a local network. It is specifically designed to help simplify
implementation of interprocess communication primitives. The layer plays a
vital role in helping achieve network transparency by reducing the perfor-
mance gap between local and remote operation. In addition, the layer insu-
lates implementation of remote operation in the kernel from changes in the
underlined network hardware. Different models of interprocess communica-
tion such as Remote Procedure Call, Data Rendezvous and Send-Receive Reply
can be easily implemented using the layer.
In this talk we provide the motivation for this unique transport
layer, define its interface and discuss its implementation. We also show
how the layer is used to implement the Send-Receive Reply model of inter-
process communication.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,ihnp4,linus,utzoo}!utcsri!clarke