clarke@csri.toronto.edu (Jim Clarke) (11/19/88)
(RS = Rosebrugh Building, 8 Taddle Creek Road)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
THEORY SEMINARS: Monday, December 5, 10 a.m. in RS 208
Tuesday, December 6, 3 p.m. in SF 1013
Thursday, December 8, 3 p.m. in GB 221
-- Michael Sipser: "Applying the Infinite in Complexity Theory"
COLLOQUIUM - Tuesday, December 6, 11 a.m. in SF 1105 -- Matthias Jarke:
"Database Support for Case"
-----------------------
THEORY SEMINARS - AN ITRC VISIT
Monday, December 5, 10 a.m. in RS 208
Tuesday, December 6, 3 p.m. in SF 1013
Thursday, December 8, 3 p.m. in GB 221
Michael Sipser
Math Dept., MIT
"Applying the Infinite in Complexity Theory"
Problems in complexity theory often concern the asymptotic behavior of fin-
ite objects as their size grows. Sometimes we may be able to gain insight
into this behavior by examining limiting objects of infinite size. In
these talks we will present two applications of this idea.
I. Analytic sets as an analog to NP
It is easily seen that the NP sets are given by nondeterministic depth
two circuits of polynomial size. If we take instead circuits of
countably infinite size, the we get what are commonly called the Ana-
lytic sets. We will give a new combinatorial proof of the classical
theorem that the Analytic sets are not closed under complement. This
proof may suggest a way to pursue the NP =? co-NP problem.
II. The Gabber-Galil explicit construction of expander graphs.
Expanders are a type of graph with numerous applications. It is easy
to see that they exist using a probabilistic argument. A number of
people have given explicit constructions for these graphs, generally
using sophisticated methods. The method of Gabber-Galil is to first
give a explicit construction of a type of infinite expander graph and
then use this to get a construction for finite graphs. We will give a
self-contained, accessible presentation of their proof.
(In addition to the above three formal seminars, there will also be infor-
mal discussions. Please let Professor Borodin know if you wish to meet
with Professor Sipser.)
COLLOQUIUM - Tuesday, December 6, 11 a.m. in SF 1105
Matthias Jarke
University of Passau, W. Germany
"Database Support for Case"
CASE tools are being developed for all phases of the software life cycle,
ranging from problem conception to system usage and maintenance support.
It is not clear, however, how these tools can be brought to bear effec-
tively in an integrated development environment, nor what kind of knowledge
about software documents, software processes, tools, developers and users
is required for such an environment, especially when dealing with very
large systems. Although this looks like a natural application for database
technology, there are good reasons why the majority of CASE environments
are still working with file systems. The database community has responded
to this challenge with several efforts to extend database semantics and
functionality with object-oriented and rule-based mechanisms to handle
software-specific issues such as teamwork, version, and configuration con-
trol. The talk describes some of these efforts and argues for a semantic
data model of information systems development processes, based on experi-
ences in the DAIDA project.
--
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