clarke@csri.toronto.edu (Jim Clarke) (11/14/88)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
AI SEMINAR - Thursday, December 1, 11 a.m. in Room SF 1105 -- James J. Little:
"Algorithmic Techniques for Vision on A Fine-grained Parallel Machine"
THEORY SEMINAR - Thursday, December 1, 3 p.m. in Room GB 221 -- Michael Kearns:
"Cryptographic Limitations on Learning
Boolean Formulae and Finite Automata"
------------------------
AI SEMINAR - Thursday, December 1, 11 a.m. in Room SF 1105
James J. Little
University of British Columbia
"Algorithmic Techniques for Vision on A Fine-grained Parallel Machine"
We described algorithms for several problems from computer vi-
sion, and illustrate how they are implemented using a set of
primitive parallel operations. The primitives we use include
general permutations, grid permutations, and the scan operation -
a restricted form of the prefix computation. We cover well known
problems allowing us to concentrate on the implementations rather
than the problems. First, we describe some simple routines such
as border following, computing histograms and filtering. We then
discuss several modules built on these routines including edge
detection, Hough transforms, and connected component labeling.
Finally, we describe how these modules are composed into higher
level vision modules.
By defining the routines using a set of primitives opera-
tions we abstract away from a particular architecture. In par-
ticular, we do not have to worry about features of machines such
as the number of processors or whether a tightly connected archi-
tecture has a hypercube network or a 4-dimensional grid network.
We do, however, still need to worry about the relative perfor-
mance of the primitives on particular machines. We discuss the
tradeoffs among primitives and try to identify which primitives
are most important for particular problems. All the primitives
discussed are supported by the Connection Machine (CM), and we
outline how they are implemented. We have implemented most of
the algorithms we describe on the connection Machine.
THEORY SEMINAR - Thursday, December 1, 3 p.m. in Room GB 221
Michael Kearns
Harvard University
"Cryptographic Limitations on Learning
Boolean Formulae and Finite Automata"
In this talk we show that the problem of inferring Boolean formu-
lae or finite automata from examples is computationally as
intractable as deciding quadratic residuosity, inverting the RSA
encryption function, and factoring Blum integers (composite
numbers of the form pq, where p and q are primes congruent to 3
mod 4). These results hold regardless of the hypothesis represen-
tation used by the learning algorithm, even if the desired accu-
racy of the hypothesis is only slightly better than 1/2. We
apply this result to show that the problem of exactly identifying
finite automata from examples and equivalence queries is hard,
and give examples of natural optimization problems, including a
generalization of graph coloring, that cannot be approximated
within any polynomial factor under standard cryptographic assump-
tions.
(Joint research with L.G. Valiant.)
--
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