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