[ont.events] U of Toronto Computer Science activities, Dec. 5-9

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