phyllis (03/22/83)
UofT Department of Computer Science Seminar Schedule for the week of March 28, 1983 Tuesday, March 29th, 4:00 P.M., SF1105: Professor Barbara Liskov, MIT Laboratory for Computer Science: "ARGUS: Linguistic Support for distributed computing". [Coffee and cookies will be served served at 3:30 P.M. in SF3205.] Wednesday, March 30th, 4:00 P.M., GB248: Dr. Domenico Sacca, CRAI, Rende, Italy: "Closure of database hypergraphs". Thursday, March 31st, 3:00 P.M., GB248: Dr. Peter de Ruda, UofT, Chemical Engineering Department: "Numerical simulation of steam injection into a heavy oil reservoir".
phyllis (04/04/83)
UofT Department of Computer Science Seminar Schedule for the week of April 11, 1983 Tuesday, April 12th, 4:00 P.M., SF1105: Professor Zvi M. Kedem, Dept. of Computer Science, State University of New York at Stony Brook: "Optimal allocation of computational resources in VLSI". Thursday, April 14th, 4:00 P.M., SF1101: Mr. Robert N. Nix, Dept. of Computer Science, Yale University: "Editing by example".
phyllis (04/14/83)
UofT Department of Computer Science Seminar Schedule for the week of April 18, 1983 Tuesday, April 19th, 3:00 P.M., GB119: Professor Derick Hood, Computer Science Department, University of Waterloo: "Computer graphics in flatland and solidland". Tuesday, April 19th, 4:00 P.M., GB119: Mr. Alan M. Frisch, Computer Science Department, University of Rochester: "Knowledge retrieval as specialized inference". Thursday, April 21st, 4:00 P.M., GB119: Professor James Foley, Department of Electrical Engineering and Computer Science, The George Washington University, Washington, D.C.: "User interface management systems".
phyllis (04/20/83)
UofT Department of Computer Science Seminar Schedule for
the week of April 25, 1983
Thursday, April 28th, 4:00 P.M., GB120: Dr. Lars Kahn, IBM San Jose
Laboratory: "PROLOG as a language for information modelling in
first order logic".
Friday, April 29th, 4:00 P.M., GB120: Professor Eric Bach, Computer
Science Division, University of California, Berkeley, California: "How
to generate random integers with known factorization".
ABSTRACT: Recent work in public-key crypography has led to
the need to generate large random numbers with known factorization.
This talk describes a probabilistic algorithm that produces a
random k-bit integer in factored form. Each such number is
equally likely to appear.
The expected running time is, up to a constant factor, that required
for k prime tests on k-bit integers. Thus, under reasonable
assumptions about the speed of primality testing, it is a polynomial
time process.phyllis (04/25/83)
UofT Department of Computer Science Seminar Schedule for
the week of May 2nd, 1983
Monday, May 2nd, 4:00 P.M., SF1105: Dr. Theo Pavlidis, Bell Laboratories,
Murray Hill, New Jersey: "Curve fitting with conic splines".
ABSTRACT: Conic splines are formed by arcs of conics, each
defined by its endpoints and the tangents at them plus an
intermediate point. Instead of the common general equation
that depends on five parameters, an equation with a single
parameter is used, thus simplifying significantly the curve
fitting problem. The resulting guided conics resemble Bezier
polynomials and for parabolas are identical to them. Such
splines can be used conveniently both for interactive design
and for automatic curve fitting. They allow circular,
elliptical and hyperbolic arcs to be included in the spline
family, while the common forms using a B-spline basis include
only parabolic arcs. Conic splines are described either in a
rational parametric or algebraic form f(x y) = 0. A simple
estimate for the distance of a point from such a curve is
given and is used to test the quality of approximations.
The data to be fitted are first approximated by a polygon, and
then simple heuristics are used to decide which sequences of
vertices should be approximated by conics. The conics found by
the applications of the heuristics are usually close approximations
of the data and need no further adjustments. When adjustments
are needed the interval is split and a conic is fitted on each
part. It is shown theoretically, that exact knot placement at
the optimal locations is less important for higher order splines
than for polygons. Examples of application of the method to
the fitting of font and other contours are given. Comparisons
with other methods suggest that conic splines require no more
than knots than cubic splines for similar quality of approximation.
Tuesday, May 3rd, 4:00 P.M., SF1105: Professor A.K. Lenstra, Mathematisch
Centrum, Amsterdam, Holland: "Recent developments in primality testing".
ABSTRACT: Until recently it could have taken a very long time
to give a rigorous proof of the primality of an arbitrary
200-digit prime number. This situation changed in 1980 when a
new primality-test was invented by L. Adleman and R. Rumely.
A simplified version of their algorithm, due to H.W. Lenstra, Jr.
and H. Cohen, was implemented on a CDC Cyber 170-750 computer in
Amsterdam; 200-digit numbers can now be handled within approximately
ten minutes. In this talk this algorithm and its implementation
will be discussed.phyllis (05/16/83)
UofT Department of Computer Science Seminar Schedule for the week of May 6th, 1983 Tuesday, May 17th, 3:00 P.M., SF3201: Professor Dominique DeWerra, Department of Mathematics, Ecole Polytechnique Federal de Lausanne, Switzerland (visiting University of Waterloo): "Matching and stable sets in graphs". ABSTRACT: During the first part of the talk one will show how some pseudo Boolean concepts may suggest an approach to the stability number of a graph. A reduction technique will be described which associates with a graph, another graph with stability number exactly one less. Extensions to hypergraph will be discussed. The second part of the talk will consist of a variation on Konig's theorem for maximum matching in a bipartite graph.
phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (05/27/83)
UofT Department of Computer Science Seminar Schedule for
the week of June 6th, 1983
Monday, June 6th, 2:00 P.M., SF1102, Professor Silvio Micali, Dept.
of Computer Science, University of Toronto: "Probabilistic Signatures".
ABSTRACT: We present a new non-deterministic way of producing
digital signatures. The signatures of a message m will depend
on m and on a sequence of coin tosses.
Signatures are easy to verify but hard to forge: After you
give your enemy the signatures of some messages of his choice,
the time that he will need to forge the signature of a new
message equals the time necessary to factor a large integer.
The proof holds for all possible message spaces.phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (05/30/83)
UofT Department of Computer Science Seminar Schedule for the week of May 30th, 1983 Thursday, June 2nd, 2:00 P.M., SF1102: Professor Dario Bini, Dept. of Mathematics, University of Pisa, Italy: "Computational complexity, commutativity, and approximation". ABSTRACT: It is well-known that the computational complexity of a problem can be reduced either by allowing the commutative law or by using approximate algorithms. Introducing the concept of commutative rank and commutative border rank of a tensor, we state some lower bound criteria for the commutative and approximate complexity of evaluating sets of bilinear forms. We show that n/2(m+1) nonscalar multiplications are necessary and sufficient to approximate the of an mxn matrix and an n-vector, while mn are needed if either approximation or commutativity is disallowed. As a consequence, we show that the 2x2-matrix-vector product can be approximated by 6 nonscalar multiplications--while 7 are necessary without approximation--and that a value of a polynomial of degree n can be approximated using n/2 + 2 multiplications.
phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (06/13/83)
UofT Department of Computer Science Seminar Schedule for
the week of June 13th, 1983
Thursday, June 16th, 3:00 P.M., SF1101: Dr. Philip Rabinowitz, The
Weizmann Institute of Science, Rehovot, Israel: "Software for
multiple numerical integration".
Thursday, June 16th, 4:00 P.M., SF1105: James R. Cordy, Computer
Systems Research Group, University of Toronto, "An orthogonal
model for code generation".
ABSTRACT
Code generation is the part of programming language com-
pilation which is concerned with choosing the actual imple-
mentation of programming language constructs in terms of
computer hardware. We can characterize the code generation
problem as a mapping from the abstract, mathematical world
of programming languages to the concrete, discrete world of
computing machines. Objects in each of these worlds can be
expressed in terms of two fundamental concepts: operators
and operands.
Viewed in this way, every existing systematic approach to
code generation is based on the same model. This tradition-
al model begins by decomposing abstract operand structure
into sequences of abstract operators. Machine implementation
is then accomplished as a single complex process which tends
to obscure the mapping between language objects and their
machine representation.
We propose a new model, which we call the orthogonal
model, which separates the implementation of abstract opera-
tors and abstract operands into two essentially independent
parts. In the orthogonal model, abstract operand structure
is left intact until implementation of abstract operators is
complete. It then remains to implement abstract operands as
a separate step.
We present a code generator structure based on this
model, which is simpler and more easily understood than ex-
isting structures. We present fundamental algorithms of the
orthogonal code generator and show how these algorithms can
be easily parameterized across a large class of target com-
puters.
Friday, June 17th, 3:00 P.M., SF1105: Professor Pavol Hell, Department
of Computer Science & Mathematics, Simon Fraser University: Generalized
matchings in graphs".phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (06/20/83)
UofT Department of Computer Science Seminar Schedule for the week of June 20th, 1983 Thursday, June 23rd, 2:00 P.M., SF1105: Bruce Char, Department of Computer Science, University of Waterloo: "Maple, a computer algebra system". ABSTRACT Maple is an interactive system for symbolic mathematics being developed at Waterloo. It builds upon the experience of the past ten years' effort on systems such as Macsyma, Reduce and MuMath. Maple provides facilities for algebraic calculations: arithmetic with rational numbers and functions, and the basic operations of symbolic differentiation, and Taylor series. There are also library packages, written in the user-level programming language provided with the system, which provide facilities for simplification of rational expressions (g.c.d.s. and polynomial factorization), solving systems of linear equations, arbitrary precision floating point arithmetic, symbolic integration, etc. Maple (version 3.0) is currently operational on Honeywell GCOS-8, Berkeley Vax/Unix and a Spectrix Xenix/68000 system. In addition to presenting examples of Maple usage, we will discuss the original design goals of the Maple project, and briefly describe some of the implementation details of the system, including data structures, the use of hashing for efficient data access, and the approach to portability. Thursday, June 23rd, 4:00 P.M., SF1105: Professor R. Nigel Horspool, School of Computer Science, McGill University: "Automatic selection of optimal code templates". ABSTRACT The development of general, machine-independent, code generation techniques in compilers has received much attention in recent years. This talk will promote a code generation philosophy that is a generalization of the old notion of code templates. With our proposed approach, the code generation problem is effectively reduced to choosing minimum cost labellings of expression trees. A practical algorithm to search for these labellings will be described. Our approach is superior, in some respects, to competing methods because more general code structures can be created. Some experience with this technique in a Pascal compiler will be discussed.
phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (07/05/83)
UofT Department of Computer Science Seminar Schedule for
the week of July 11th, 1983
Monday, July 11th, 4:00 P.M., SF3202: Mr. Larry O'Gorman, Computer Science
Department, Carnegie-Mellon University, Pittsburgh, Pa.: "Image segmentation
and classification with application to automated histopathology."
--
Phyllis Eve Bregman
CSRG, Univ. of Toronto
{linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!phyllisphyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (08/31/83)
UofT Department of Computer Science Seminar Schedule for
the week of September 5th, 1983
Wednesday, September 7th, 4:00 P.M., Rosebrugh 211: Professor J.E. Dennis,
Dept. of Mathematical Sciences, Rice University, Houston, Texas:
"A user's guide to optimization algorithms".
**GOAL**
To provide a user's introduction to the basic ideas currently favored
in optimization routines by numerical analysts. I will use nonlinear
least squares as an example, and I will stress methods for improving
a poor initial solution estimate because it is a popular misconception
that optimization routines need good guesses.
--
Phyllis Eve Bregman
CSRG, Univ. of Toronto
{linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!phyllisphyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (10/05/83)
UofT Department of Computer Science Seminar Schedule for
the week of October 10th, 1983
Thursday, October 13th, 2:00 P.M., GB248: Professor Susan Landau,
Department of Mathematics, Wesleyan University, Middleton, Conn.,
"Solvability by radicals is in polynomial time".
ABSTRACT: Determining if a polynomial has roots expressible in
radicals is a question whose history goes back to the Babylonians.
Galois provided a constructive (through exponential time) criterion
for determining which polynomials have roots expressible in radicals.
We provide a polynomial time algorithm to answer the question.
(This talk represents joint work with Gary Miller.)
Thursday, October 13th, 3:00 P.M., GB248: Margaret Solowiej, Department
of Computer Science, University of Toronto, "N-dimensional Newton
method with precision control for determining roots of complex
polynomials".
ABSTRACT: Difficulties with deflation, stopping criteria and limited
precision in conventional root-finding algorithms lead to their
failure to return roots to within a prescribed accuracy. An algorithm
is presented which uses the n-dimensional Newton method with dynamic
precision control for determining all the roots of a complex polynomial
simultaneously, to within a user-specified tolerance. Control of
precision is accomplished by using a running error analysis to
monitor the errors in the approximation updates at each iterative step.
Friday, October 14th, 11:10 A.M., GB220: Professor Neil Immerman,
Departments of Math and Computer Science, Yale University, New Haven,
Conn., "Languages which capture complexity classes".
ABSTRACT: We present a series of languages adequate for expressing
exactly those properties checkable in a series of computational
complexity classes. For example, we show that a graph property is
in polynomial time if and only if it is expressible in the language
of first order graph theory together with a least fixed point operator.
As another example, a group theoretic property is in the logspace
hierarchy if and only if it is expressible in the language of first
order group theory together with a transitive closure operator.
Thus questions of complexity can be translated to expressibility issues.
Separating complexity classes is equivalent to showing that certain
of the above operators are more powerful than others. Efficient
algorithms may be obtained simply by describing a problem in one of
our languages.
--
Phyllis Eve Bregman
CSRG, Univ. of Toronto
{decvax,linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!phyllisphyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (10/13/83)
UofT Department of Computer Science Seminar Schedule for
the week of October 17th, 1983
Thursday, October 20th, 11:00 P.M., GB248: Professor Hanan Samet
Department of Computer Science, University of Maryland, College
Park, MD., "An overview of quadtree research".
ABSTRACT: Region representation is an important issue in image processing,
cartography, and computer graphics. A wide number of representations
is currently in use. Recently, there has been much interest in a
hierarchical data structure termed the quadtree. It is compact and,
depending on the nature of the region, saves space as well as time and
also facilitates operations such as search. In this talk we give a
brief overview of the quadtree data structure and related research
results.
[Coffee and cookies will be served at 10:30 A.M. in SF3205.]
Thursday, October 20th, 3:00 P.M., GB248: Dr. Howard Elman, Department
of Computer Science, Yale University, New Haven, CT., "Iterative
methods for large sparse systems of linear equations".
ABSTRACT: We discuss recent progress made in solving sparse linear
systems by iterative methods. We give a brief overview of methods
for symmetric positive-definite linear systems, and then describe current
research on methods for nonsymmetric systems. This work focuses on
the combination of Krylov subspace methods, including both adaptive
and conjugate gradient-like methods, and preconditioning techniques such
as incomplete factorizations and fast direct methods. We describe both
theoretical analysis and numerical experiments.
--
Phyllis Eve Bregman
CSRG, Univ. of Toronto
{decvax,linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!phyllis