clarke@csri.toronto.edu (Jim Clarke) (04/06/89)
SUMMARY:
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
AI SEMINAR - Thursday, April 20, 11 a.m. in Room SF 1105 -- Avi C. Kak
"Research Issues in 3-D Robotic Vision"
THEORY SEMINAR - Thursday, April 20, 3 p.m. in Room GB 244 -- Mario Szegedy
"Multiparty Protocols and Logspace-Hard Pseudorandom Sequences"
----------------
AI SEMINAR - Thursday, April 20, 11 a.m. in Room SF 1105
Avi C. Kak
Purdue University
"Research Issues in 3-D Robotic Vision"
The speaker will first survey the state-of-the-art in passive approaches to
3-D robotic vision, emphasizing what has been done so far in binocular
stereopsis for depth perception. The deficiencies of the purely bottom-up
approaches will be highlighted and the limitations of what we currently
know about injecting high-level object knowledge into the algorithms
pointed out. A rule-based approach for integrating the various paradigms
for binocular stereopsis will also be discussed.
The second half of the talk will focus on active approaches, especially
those employing structured-light and laser-radar for depth perception. The
speaker will mention the computational complexity issues involved in
model-based object interpretation strategies. The subject of modeling 3-D
objects will also be broached. Finally, the speaker will address the topic
of recognizing generic 3-D shapes.
THEORY SEMINAR - Thursday, April 20, 3 p.m. in Room GB 244
Mario Szegedy
University of Chicago
"Multiparty Protocols and Logspace-Hard Pseudorandom Sequences"
We show that constructing certain families of graphs can help in defining
functions with high k-ways communication complexity. The k-ways
communication complexity of a function with respect to a k-partition of the
input bits is defined as the number of bits k parties have to exchange
according to a certain protocol if the parties know each but one input
segment and want to evaluate the function. Note that this is a direct
generalisation of the usual 2-ways communication complexity. The bounds
will hold even if the parties wish to have only a 1% advantage at guessing
the values of the function. As an application we construct a pseudorandom
generator for Logspace, a corollary of which is an explicit universal
sequence of subexponential length. We also apply the multiparty protocol
lower bounds to derive new time-space tradeoffs. We give a tight time-
space tradeoff of the form TS = THETA (n**2) for general, k-head
Turing-Machines; the bounds hold for a function that can be computed in
linear time and constant space by a k+1 head Turing-Machine.
(Joint work with Laszlo Babai and Noam Nisan)
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
clarke@csri.toronto.edu or clarke@csri.utoronto.ca
or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke