clarke@csri.toronto.edu (Jim Clarke) (02/06/89)
ACTIVITIES FOR THE WEEK COMMENCING FEBRUARY 20, 1989
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
COLLOQUIUM - Tues., Feb. 21, 11 a.m. in Room SF 1105 -- Martin Tompa
"Zero Knowledge Interactive Proofs (A Digest)"
AI/THEORY SEMINAR - Tues., Feb. 21, 2 p.m. in Room GB 244 -- Eric Sven Ristad
"The Complexity of Human Language Comprehension"
SYSTEMS SEMINAR - Wednes., Feb. 22, 2 p.m. in Room SF 3202 -- Joseph R. Falcone
"Research Issues in Storage Systems"
AI SEMINAR - Thurs., Feb. 23, 11 a.m. in Room SF 1105 -- Benjamin Kuipers
"Qualitative Reasoning: Modeling and Simulation with Incomplete Knowledge"
THEORY SEMINAR - Thurs., Feb. 23, 3 p.m. in Room GB 244 -- Valerie King
"The Set-Maxima Problem"
---------------------------
COLLOQUIUM - Tuesday, February 21, 11 a.m. in Room SF 1105
Martin Tompa
Mathematical Sciences
Thomas J. Watson Research Center
"Zero Knowledge Interactive Proofs (A Digest)"
A "zero knowledge interactive proof" is a protocol whereby one
party attempts to convince another of the validity of a state-
ment, without revealing any information beyond this one bit.
This concept has recently been proven important in cryptographic
and distributed protocols.
This talk will motivate and present the concept, together with
examples. The talk is self-contained, and appropriate for a gen-
eral computer science audience.
AI/THEORY SEMINAR - Tuesday, February 21, 2 p.m. in Room GB 244
Eric Sven Ristad
MIT Artificial Intelligence Lab
"The Complexity of Human Language Comprehension"
In this talk I will examine the computational problem of human
language comprehension: what linguistic representation is as-
signed to a given sound? This language comprehension problem may
be factored into smaller, interrelated (but independently stat-
able) problems defined on partial linguistic representations. For
example, in order to understand a sound, the listener must assign
a phonetic form to the sound; determine the morphemes that com-
pose the words in the sound; and calculate the linguistic an-
tecedent of every pronoun in the utterance.
I will prove that these and some other subproblems are all NP-
hard, and that language comprehension is itself PSPACE-hard, ac-
cording to current linguistic theory.
This research reveals the underlying computational structure of
several complex linguistic interactions; raises the fundamental
question of how language can be at once so complex and yet so
easy to use; and suggests that a computational approach to human
language might succeed where other approaches have inevitably
failed.
SYSTEMS SEMINAR - Wednesday, February 22, 2 p.m. in Room SF 3202
Joseph R. Falcone
Digital Equipment Corporation
"Research Issues in Storage Systems"
A crisis is developing in Storage Systems technology (the entire
path from user I/O request to media) as distinguished from
Storage Components (the mechanisms used to store data on media).
The performance and functionality of Storage Systems are not
keeping up with that of Computer Systems.
While this is not an entirely new development for the industry,
the advent of multi-MIPS PC and workstation systems is bringing
this storage crisis to every desktop and even into the home. Ad-
ding to this problem is the fact that Storage Systems research is
considered a low-tech backwater by the majority of professionals.
The talk will dispel this myth, and describe the many interest-
ing, practical research areas in Storage Systems including
storage protocols, disk array technology, cache management,
hierarchical storage management, and backup & disaster recovery
among others. The talk will conclude with a brief discussion of
the IEEE-CS Reference Model for Mass Storage Systems.
AI SEMINAR - Thursday, February 23, 11 a.m. in Room SF 1105
Benjamin Kuipers
The University of Texas at Austin
"Qualitative Reasoning: Modeling and Simulation
with Incomplete Knowledge"
Qualitative reasoning is a collection of methods for building and
simulating models of physical systems in spite of incomplete
knowledge. The QSIM representation allows models to be expressed
in the form of qualitative differential equations, which allow
incompletely known functional relations to be described only as
monotonically increasing or decreasing. Region transitions make
it possible to describe discontinuous change or change of model-
ing perspective. The QSIM algorithm for qualitative simulation,
which derives behavior predictions from the qualitative model
representation, is both highly efficient and mathematically
sound.
In recent work, we have concentrated on extending early ``limit
analysis'' methods for qualitative simulation to more sophisti-
cated methods capable of simulating realistic systems.
- We have developed a method for reasoning with incomplete
quantitative knowledge, to detect and exclude behaviors that are
qualitatively plausible but quantitatively impossible.
- We have begun to exploit the mathematical theory of dynamical
systems and the phase space representation to apply more global
constraints to the predicted behaviors, viewed as the solutions
to qualitative differential equations.
- We have developed methods for time-scale abstraction for
decomposing complex systems into hierarchies of simpler mechan-
isms operating at different time-scales. Fast mechanisms view
slower mechanisms as constant; slow mechanisms view faster ones
as instantaneous (e.g. as functional relations).
- We have implemented model-building methodologies such as de-
Kleer and Brown's device-centered ontology and Forbus' process-
centered ontology as compilers whose target representation is
QSIM.
These advances, and the research questions they raise, provide a
framework for the development of qualitative reasoning methods
with the power to handle realistic systems.
THEORY SEMINAR - Thursday, February 23, 3 p.m. in Room GB 244
Valerie King
University of Toronto
"The Set-Maxima Problem"
Given a set X of n elements from an unknown total order and m
subsets of X, we wish to find the maximum element of each subset,
where cost is determined by the number of comparisons required
between elements of X. One simple method is to sort the elements
of X with O(n lg n) comparisions. Can one do better? In particu-
lar, if m=n, will a linear number of comparisons suffice?
These questions remain open for deterministic strategies. I will
talk about a randomized algorithm which uses an expected number
of O(n(log n)^1/3) comparisons.
(Joint work with Claire Kenyon-Mathieu)
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
clarke@csri.toronto.edu or clarke@csri.utoronto.ca
or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke