[ont.events] U of Toronto Computer Science activities, March 14-18

clarke@csri.toronto.edu (Jim Clarke) (03/07/88)

         (SF = Sandford Fleming Building, 10 King's College Road)
              (GB = Galbraith Building, 35 St. George Street)
               (WB = Wallberg Building, 184 College Street)

SUMMARY:

NUMERICAL ANALYSIS SEMINAR, Tuesday, March 8, 10 am, WB242 -- Ben Leimkuhler:
     "Consistent Initialization of Differential-Algebraic Equations"

COLLOQUIUM, Tuesday, March 15, 11 am, SF1105 -- James Perdue:
     "Supercomputers, Gigabits and Graphics"

A.I. SEMINAR, Tuesday, March 15, 2 pm, SF1105 -- Bruce Porter:
     "Toward the Automatic Construction and Extension of Knowledge Bases"

GRAPHICS SEMINAR, Tuesday, March 15, 3 pm, GB120 -- Avi Naiman:
     "Fast Filtering of Characters"

A.I SEMINAR, Wednesday, March 16, 11 am, SF3202 -- Demetri Terzopoulos:
     "Deformable Models In Computer Vision And Graphics"

SPECIAL SEMINAR, Wednesday, March 16, 2 pm, SF3202 -- Gary Chapman:
     Computer Professionals for Social Responsibility

SYSTEMS SEMINAR, Thursday, March 17, 11 am, SF1101 -- Boris Kogan:
     "Bakunin Data Networks: An Approach To Designing
                  Highly Available Replicated Databases"

THEORY SEMINAR, Thursday, March 17,  3 pm, GB244 -- Selim Akl:
     "Hierarchical Cryptology"

THEORY SEMINAR, Friday, March 18, 3 pm, GB220 -- Marc Snir:
     "Complexity Theory of Parallel Efficient Algorithms"

---------------------------------

        NUMERICAL ANALYSIS SEMINAR, Tuesday, March 8, 10 am, WB242

                            Dr. Ben Leimkuhler
                          University of Illinois

      "Consistent Initialization of Differential-Algebraic Equations"

Differential-algebraic  equations   (DAEs)   occur   when dynamic
phenomena  are  modeled subject to constraints.  Many methods (backward
differentiation  formulas,  implicit  Runge- Kutta,  etc.)  are  now  known
to  be  convergent for certain classes of DAEs.  However the study of the
formal  convergence behavior  of  such  methods has only served to point
out other barriers to their robust implementation.  In  particular,  the
assumption  (reasonable  for ODEs) that the initial values are known is
unreasonable when constraints are present.   In  this talk,  we  show  how
the  constraints (and their derivatives) place a burdensome  consistency
requirement  on  the  initial values.   We outline a general method, based
on finite differences, for satisfying this consistency requirement,  and
discuss its applicability to certain classes of DAEs.

               COLLOQUIUM, Tuesday, March 15, 11 am, SF1105

                             Dr. James Perdue
                        Ultra Network Technologies

                  "Supercomputers, Gigabits and Graphics"

A scientist's productivity is often limited by the tools at his disposal.
Supercomputing has provided the researcher with a very valuable tool for
solution of complex, multi-variable, multi-dimensional problems.  However,
the ability to become productive still depends on getting access to the
results in a timely manner.  Advances in network performance have lagged
considerably behind advances in Supercomputing performance.  In fact, over
the past 10 years, supercomputing power has increased greater than a factor
of 10 with no real increase in network performance.  The advent of high
resolution graphics technology has created a new toolbox for the visualiza-
tion of results.  These graphics tools require high performance networking
in the gigabit per second range to permit practical applications to be
developed.  The use of high performance networks is explored here in vari-
ous applications.  The factors that affect network performance in the
gigabit/sec range are described.  Further, the architecture required to
support such applications is presented in the context of today's network
standards and technology, including ISO TP4, TCP/IP and FDDI.

               A.I. SEMINAR, Tuesday, March 15, 2 pm, SF1105

                          Professor Bruce Porter
                       University of Texas at Austin

                           "Toward the Automatic
              Construction and Extension of Knowledge Bases"

This talk describes two programs resulting from our research in machine
learning.  The first, called Protos, is a learning apprentice which
acquires knowledge for performing heuristic classification.  We have
applied Protos to the domain of clinical audiology.  Our domain expert
trained Protos with explained examples without the involvement of a
knowledge engineer. Through this interaction, Protos has evolved into an
expert system which correctly classifies and explains 98% of new cases and
continues to learn during its use.

Building Protos has forced us to scrutinize the usefulness of inductive
learning and deductive classification.  These inference methods have been
widely studied in machine learning; however, their seductive elegance in
artificial domains (e.g., mathematics) does not carryover to natural
domains (e.g., medicine).  In the Protos system, we relegate inductive
learning and deductive classification to minor roles that support retain-
ing, indexing, and matching exemplars.

The second program is a knowledge-rich learner.  We believe that learning
involves integrating new information into an existing base of knowledge;
learning takes place at the "fringes of knowledge." While this conjecture
seems obvious, most machine learning programs, such as Protos, are largely
ignorant.  We are constructing a large-scale structured knowledge base in
the domain of plant anatomy and physiology using Lenat's CYC system.  Our
learning program uses the knowledge base to explain (for itself) the plau-
sibility of information from the teacher.  Explanations integrate the new
information into the expanding knowledge base and motivate follow-up ques-
tions and conjectures.

             GRAPHICS SEMINAR, Tuesday, March 15, 3 pm, GB120

                                Avi Naiman
                           University of Toronto

                      "Fast Filtering of Characters"

The  availability  of  extremely  fast  processors  and   high- resolution
graphics  devices  such  as  display  screens,  laser printers, and film
recorders, has led to increased  investigation into  the  way  characters
are designed, stored, and processed by computers.  We will provide an over-
view of the  fundamental  concepts in Digital Typography, including Letter-
form Design, Optical Considerations, and the Output Medium.

We will then discuss one approach to improving the  quality  of digital
fonts  on  relatively low-resolution devices, namely the use of grayscale
characters.  By incorporating gray pixels in the character  representation
- in addition to black and white ones - we can increase the effective reso-
lution of digital fonts.  While grayscale  characters  can be produced by
filtering bi-level masters, most of the efficient filtering techniques
known in Computer Graphics cannot directly be applied.  For example,
prefiltering is impractical, due to the number of  character  masters  and
the requirement of sub-pixel positioning.

We will present a fast filtering technique  especially  adapted to this
task.  The characters are decomposed into rectangles, and a summed-area
representation of the  filter  is  convolved  efficiently with each indivi-
dual rectangle to construct the grayscale character.  For a given  filter,
the  number  of  operations  is O(linear size of the grayscale character),
which is optimal.  The performance of the implementation is such that
filtering  characters for  grayscale displays is feasible in realtime on
personal workstations.

              A.I SEMINAR, Wednesday, March 16, 11 am, SF3202

                          Dr. Demetri Terzopoulos
                     Schlumberger Palo Alto Research

            "Deformable Models In Computer Vision And Graphics"

Vision and graphics are mutually converse disciplines; the former is con-
cerned with the analysis of images, the latter with their synthesis.  They
pose similar problems at the object modeling level.  I shall describe a
physically-based approach to analyzing and synthesizing the shapes and
motions of nonrigid objects. Objects are modeled using deformable curve,
surface, and solid primitives, while constraints are represented as dynamic
forces applied to these primitives.  In the context of graphics (the direct
problem), realistic images of flexible objects may be synthesized when the
applied forces arise from the interaction of deformable models with simu-
lated physical environments.  With regard to vision (the inverse problem),
deformable models may be used to infer the shapes and motions of objects
from their images.  Here the forces are derived from natural image data and
enforce image-based constraints.  They actively shape and move models to
achieve maximal consistency with imaged objects of interest and to maintain
the consistency over time.  I will present results of applying deformable
models to image contour extraction, stereo and motion correspondence match-
ing, static 3D object reconstruction from monocular images, and the
recovery of 3D shape and nonrigid motion of objects from dynamic stereo
imagery. The video presentation will include computer animations of deform-
able models reacting to a variety of simulated physical phenomena.

            SPECIAL SEMINAR, Wednesday, March 16, 2 pm, SF3202

                             Mr. Gary Chapman
              Computer Professionals for Social Responsibility

CPSR membership and chapters - have been growing steadily.  It now has a
considerable range of activities besides conducting a critique of the Stra-
tegic Defense Initiative (Star Wars) that was its first major interest.
Gary will describe the structure of the organization and the scope of its
concerns.

            SYSTEMS SEMINAR, Thursday, March 17, 11 am, SF1101

                              Dr. Boris Kogan
                           Princeton University

             "Bakunin Data Networks: An Approach To Designing
                  Highly Available Replicated Databases"

Data replication in distributed databases is used to improve data availa-
bility and provide faster read access.  However, new problems for database
management are introduced due to the need for maintaining the consistency
of replicated copies. Dealing with communication failures is one of them.
For example, when the network partitions, continued update activities may
lead to data inconsistency. On the other hand, halting all updates until
the network is reconnected is undesirable in many cases.

This talk will describe a methodological framework for designing replicated
databases that exhibit a high degree of availability (including the ability
to make updates) in the face of communications failures that can partition
the network.  The framework is based on the simple notions of fragments and
agents. It gives rise to a wide scope of options with varying degrees of
data consistency and availability. The consistency criteria offered by
these options include one-copy serializability as well as two new criteria:
virtual serializability and fragmentwise serializability.

             THEORY SEMINAR, Thursday, March 17,  3 pm, GB244

                            Professor Selim Akl
                            Queen's University

                         "Hierarchical Cryptology"

Assume a communication system where every user belongs to one of a number
of disjoint security classes Ui, and periodically receives data from
an authority U0.  The set of classes is partially ordered by the
relation <=, where Ui <= Uj means that users in Uj can have access to
information destined to users in Ui.  By definition, every class Ui in the set
is such that Ui <= U0.  The problem is to design a scheme such that an object
x broadcast by U0 and addressed to users in Um is accessible to users in Ui
if and only if Um <= Ui.

Various aspects of this problem will be addressed in the talk, and a number
of cryptographic solutions will be described.

               THEORY SEMINAR, Friday, March 18, 3 pm, GB220

                               Dr. Marc Snir
                       IBM Thomas J. Watson Research

           "Complexity Theory of Parallel Efficient Algorithms"
-- 
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