clarke@csri.toronto.edu (Jim Clarke) (09/28/88)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
(WB = Wallberg Building, 184 College Street)
SUMMARY:
AI SEMINAR - Thursday, October 13 at 11 a.m. in SF 1105 -- Deborah Walters:
"The Analysis of Contour Images"
AI SEMINAR - Thursday, October 20, 11 a.m. in SF1105 -- Fahiem Bacchus:
"LP, a logic for Representation and Reasoning with
Qualitative Statistical Knowledge"
THEORY SEMINAR - Friday, October 21 at 11 a.m. in WB 119 -- Michael Luby:
"Removing Randomness in Parallel Computation Without a Processor Penalty"
THEORY SEMINAR - Thursday, October 27, 3 p.m. in GB 221 -- Hugo Krawczyk:
"On the Existence of Pseudorandom Generators"
-------------------
AI SEMINAR - Thursday, October 13 at 11 a.m. in SF 1105
Professor Deborah Walters
Department of Computer Science, SUNY/Buffalo
"The Analysis of Contour Images"
Three aspects of the analysis of contour images will be discussed.
(1) How can a contour image be rapidly segmented, and the regions likely
to contain the most useful information rapidly selected? It will be
shown how the use of features which appear to be used by the human
visual system enables simple, bottom-up algorithms to be developed
which do not require scene dependent knowledge. Such algorithms are
capable of segmenting arbitrary contour images into contour groups
which are likely to have arisen from a single object or object part.
In addition, the algorithms produce a Perceptual Significance Hierar-
chy of the image, where the top level contains only those contours
which have a high probability of being the most perceptually signifi-
cant in the image. The Perceptual Significance Hierarchy can be used
to rapidly select image regions of potential significance to later
stages of visual processing.
(2) How can image contours be detected and represented in a manner which
preserves the relevant contour features? Although many computer
vision contour detection algorithms loose image contour information
which appears to be used by the human visual system, the rho-space
algorithms can be used to detect such features of image contours. The
rho-space algorithms use contour representations which are inspired by
the orientation column architecture of the mammalian visual cortex.
(3) Finally, how can the shape of image contours be represented? In order
to perform visual tasks such as object recognition, the shape of image
contours must be represented. It will be shown that a discrete con-
tour representation, which is readily computable from the rho-space
representation, has certain useful properties including invariance
over the 2-dimensional transformations of rotation, scaling and trans-
lation.
AI SEMINAR - Thursday, October 20, 11 a.m. in SF1105
Fahiem Bacchus
Department of Computer Science, University of Waterloo
"LP, a logic for Representation and Reasoning with
Qualitative Statistical Knowledge"
Driven by a need to represent the vaguely quantified statistical
knowledge used in common sense reasoning, and the inadequacies of previous
probability logics, a new logic, called Lp, is developed. Lp is capable of
representing statistical knowledge in an efficient manner, through the for-
mation of probability terms from open formulas. By making the denotation
of these probability terms a separate sort, many forms of vaguely quanti-
fied statistical information can be efficiently represented, and reasoned
with through a sound and complete proof theory. If more exactly quantified
information is available, this too can be represented and reasoned with.
THEORY SEMINAR - Friday, October 21 at 11 a.m. in WB 119
Michael Luby
Computer Science Department, University of Toronto
(currently on leave of absence visiting ICSI)
"Removing Randomness in Parallel Computation
Without a Processor Penalty"
We develop some general techniques for removing randomness from
randomized NC algorithms without a blowup in the number of processors.
One of the requirements for the application of these techniques is that the
analysis of the randomized algorithm uses only pairwise independence. Our
main new result is a parallel algorithm for the DELTA + 1 vertex coloring
problem with running time O( log ** 3 n log log n) using a linear
number of processors on a CREW PRAM. Our techniques also apply to several
other problems, including the maximal independent set problem and the maxi-
mal matching problem. The application of the general technique to these
last two problems is mostly of academic interest because NC algorithms
that use a linear number of processors which have better running times have
been previously found.
THEORY SEMINAR - Thursday, October 27, 3 p.m. in GB 221
Professor Hugo Krawczyk
Department of Computer Science, Technion, Israel
"On the Existence of Pseudorandom Generators"
Pseudorandom generators (suggested and developed by Blum and
Micali, and Yao) are efficient deterministic programs that expand a ran-
domly selected k-bit seed into a much longer pseudorandom bit sequence
which is indistinguishable in polynomial time from an (equally long)
sequence of unbiased coin tosses. Pseudorandom generators are known to
exist assuming the existence of functions that cannot be efficiently
inverted on the distributions induced by applying the function iteratively
polynomially many times (Levin). (This generalizes previous results of
Blum-Micali and Yao). This sufficient condition is also a necessary one,
but it seems difficult to check whether particular functions, assumed to be
one-way, are also one-way on their iterates. This raises the fundamental
question whether the mere existence of one-way functions suffices for the
construction of pseudorandom generators.
In this paper we present progress towards resolving this question. We
consider 'regular functions', in which every image of a k-bit string has
the same number of preimages of length k. We show that if a regular func-
tion is one-way then pseudorandom generators do exist. In particular,
assuming the intractability of general factoring, we can now prove that
pseudorandom generators do exist. Another application is the construction
of a pseudorandom generator based on the assumed intractability of decoding
random linear codes.
Joint work with Oded Goldreich and Mike Luby.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke