clarke@utcsri.UUCP (Jim Clarke) (03/02/87)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
Tuesday, March 10, 2 pm, GB221 -- Brad A. Myers:
``The Present and Future of Window Managers"
Tuesday, March 10, 3 pm, GB120 -- Sandy Pentland:
``Recognition by Parts"
Wednesday, March 11, 3 pm, GB220 -- John Plaice:
``LUSTRE: A real time data flow language"
Thursday, March 12, 3 pm, GB220 -- Dexter Kozen:
``Polynomial Decomposition Algorithms"
-------------------
GRAPHICS SEMINAR, Tuesday, March 10, 2 pm, GB221
Mr. Brad A. Myers
University of Toronto
``The Present and Future of Window Managers"
Window managers were invented about 10 years ago at Xerox PARC. Now,
there are hundreds of different window managers running on many different
kinds of computer hardware. One surprising thing about all these window
managers is that they are actually very similar and the differences that do
exist can be broken down into a small number of choices. This observation
has led to the hope that it would be possible to create a standard window
manager that would be usable for a wide variety of computers and users.
There are at least three separate efforts at standardization: ``X",
``NeWS", and the official window management standards body: X3H3.6.
This talk will discuss the similarities and differences among window
managers, the status of efforts at standardization, and some areas where
future work is needed so the next generation of window managers will be
easier to use for both application programmers and end users.
A.I./GRAPHICS SEMINAR, Tuesday, March 10, 3 pm, GB120
Professor Sandy Pentland
SRI International
``Recognition by Parts"
A general-purpose visual system must be able to encounter an object,
learn its description, and thereafter be able to recognize it. This
requires being able to compute a CANONICAL description of the object, for
comparison to previously-learned object descriptions. In humans, seeing
objects as having ``parts" seems to be central to this learning/recognition
process. I will describe a representation for such ``parts" that is based
on prototypes and deformation processes, show that it is able to describe a
very wide range of 3-D shapes, and that such descriptions that are normally
isomorphic to people's notions of part structure. The small number of
parameters in this representation allows us to use standard model-based
machine vision techniques to recover acceptably canonical 3-D descriptions
from range data. Several examples of learning canonical shape descriptions
will be shown, using ALV range data.
SYSTEMS SEMINAR, Wednesday, March 11, 3 pm, GB220
Professor John Plaice
Laboratoire Circuit & Systemes
``LUSTRE: A real time data flow language"
THEORY SEMINAR, Thursday, March 12, 3 pm, GB220
Professor Dexter Kozen
Cornell University
``Polynomial Decomposition Algorithms"
We examine the question of when a polynomial f(x) over a commutative
ring has a nontrivial decomposition f(x) = g(h(x)). Previous algorithms by
Barton and Zippel and by Alagar and Thanh are exponential-time in the worst
case, require polynomial factorization, and only work over fields of
characteristic 0. We give a cubic-time sequential algorithm which does not
use polynomial factorization, and works over any commutative ring contain-
ing a multiplicative inverse of the degree of g. In the presence of
appropriate roots of unity, the complexity can be further reduced to qua-
dratic time. We also show that the problem is in NC. Finally, we give a
new structure theorem that leads to necessary and sufficient algebraic con-
ditions for decomposibility over any field. We apply this theorem to
obtain an NC algorithm for decomposing irreducible polynomials over finite
fields, and a subexponential algorithm for decomposing irreducible polyno-
mials over any field admitting efficient polynomial factorization. (Joint
work with Susan Landau, Wesleyan.)
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke