clarke@csri.toronto.edu (Jim Clarke) (03/02/88)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
(WB = Wallberg Building, 184 College Street)
(UC = University College, King's College Circle)
SUMMARY:
NUMERICAL ANALYSIS SEMINAR, Tuesday, March 8, 10 am, WB242 -- Yuying Li:
"An Efficient Algorith for Discrete Chebyshev Problems"
SPECIAL SEMINAR, Tuesday, March 8, 11 am, SF1105 -- James Varah:
"The Centre for Integrated Computer Systems Research"
A.I./MCLUHAN SEMINAR, Tuesday, March 8, 4-6 pm, UC179 -- Ray Jackendoff:
"Consciousness and the Computational Mind"
FIRESIDE CHAT, Tuesday, March 8, 3-5 pm, GB202 -- Gordon Lang:
"Ethics in Computer Science"
SYSTEMS SEMINAR, Thursday, March 10, 11 am, SF1101 -- Oliver Gunther:
"Representation of Geometric Data in an Extensible Database System"
THEORY SEMINAR, Thursday, March 10, 3 pm, GB244 -- Bill Aiello:
"On the Power of Interaction"
NUMERICAL ANALYSIS, Friday, March 11, 2 pm, GB220 -- Wei Pei Tang:
"Template Operators -- Fast Solvers -- Fractals"
----------------------------
NUMERICAL ANALYSIS SEMINAR, Tuesday, March 8, 10 am, WB242
Ms. Yuying Li
University of Waterloo
"An Efficient Algorith for Discrete
Chebyshev Problems"
The structure of a local minimum for discrete nonlinear Chebyshev problems
has been characterized. The characterization is described by the generali-
zation of some essential concepts, important in the design of efficient
algorithms for the L-inf problem. A new algorithm which locates a
local minimum has been designed to exploit this special structure and char-
acterization of the Chebyshev problem. The algorithm is globally conver-
gent with a superlinear convergence rate. In addition, there are exten-
sions to general minmax problems. Numerical results indicate the efficacy
of the approach.
SPECIAL SEMINAR, Tuesday, March 8, 11 am, SF1105
James Varah, Director
University of British Columbia
"The Centre for Integrated Computer Systems Research"
This presentation will introduce a newly-formed unit at UBC, whose purpose
is to facilitate and coordinate activities in computer-based research
areas. CICSR (pronounced 'Caesar') has affiliated faculty members from the
Departments of Computer Science, Electrical Engineering, and Mechanical
Engineering. Collaborative research is encouraged, as well as external
liaison with industrial firms and government agencies. The Centre has
recently been funded through the BC Government's Fund for Excellence in
Education, and is actively seeking research-oriented faculty. Special funds
are also available for graduate students, faculty, and visitors through the
BC Advanced Systems Institute.
A.I./MCLUHAN SEMINAR, Tuesday, March 8, 4-6 pm, UC179
Professor Ray Jackendoff
Brandeis University
"Consciousness and the Computational Mind"
FIRESIDE CHAT, Tuesday, March 8, 3-5 pm, GB202
Mr. Gordon Lang
Motorola Information Systems
"Ethics in Computer Science"
An event being sponsored by the Computer Science Students Union (CSSU).
Pizza and refreshments will be served. More details of the talk will be
announced later this week.
SYSTEMS SEMINAR, Thursday, March 10, 11 am, SF1101
Dr. Oliver Gunther
University of California
"Representation of Geometric Data
in an Extensible Database System"
We will present two new representation schemes for geometric
data and discuss how to embed these schemes in an extensible database sys-
tem like POSTGRES.
Convex polyhedral chains represent d-dimensional polyhedral
point sets as algebraic sums of convex polyhedra cells). Cells in turn are
represented as the intersection of a finite number of halfspaces and
stored as a ternary vector. With this approach, set operations can be
decomposed into two independent steps: (a) a collection of vector
operations, and (b) a garbage collection where those vectors are eliminated
that represent empty cells.
The arc tree is a balanced binary tree that represents a curve of
length l such that any subtree whose root is on the k-th tree level is
representing a subcurve of length l/2^k. Each tree level is associ-
ated with an approximation of the curve; lower levels correspond to
approximations of higher resolution. Based on this hierarchy of
detail, queries such as point search or intersection detection and compu-
tation can be solved in a hierarchical manner. We will present the results
of a practical performance analysis for various set and search opera-
tions and discuss several options to embed arc trees as complex objects
in an extensible database management system like POSTGRES.
We conclude with an outline how to use these results to provide effi-
cient database support for robotics and computer vision.
THEORY SEMINAR, Thursday, March 10, 3 pm, GB244
Dr. Bill Aiello
M.I.T.
"On the Power of Interaction"
Let IP[f(|x|)] be the class of languages recognized by interactive
proofs with f(|x|) interactions. Babai [B] showed that all languages
recognized by interactive proofs with a bounded number of interactions can
be recognized by interactive proofs with only two interactions; i.e., for
every constant k, IP[k] collapses to IP[2].
In this paper, we give evidence that interactive proofs with an
unbounded number of interactions may be more powerful than interactive
proofs with a bounded number of interactions. We show that for any
unbounded polynomial time computable functions f(n) and g(n) = o(f(n))
there exists an oracle B such that IP ^ B[f(|x|)] is not a subset of
IP ^ B[g(|x|)].
The techniques employed are extensions of the techniques for proving
lower bounds on small depth circuits used by Yao and Hastad.
NUMERICAL ANALYSIS, Friday, March 11, 2 pm, GB220
Dr. Wei Pei Tang
University of Waterloo
"Template Operators -- Fast Solvers -- Fractals"
A Template operator is a new structure for linear operators in finite
dimensional space. It removes the artificial sequential constraint in
matrix structure, and maintains the topological frame of the original con-
tinuous problem from which a finite dimensional linear operator is derived.
In particular, the proximity of the variables and the locality of the
operator are well maintained. Many physical phenomena can be easily inter-
preted in this structure. This structure also provides us with a useful
tool for designing new parallel algorithms.
Up to now, the best direct approach for solving the model problem has
complexity of O(N loglog (N) ), where N is the number of unknowns. Using
template operators, an optimal fast solver with complexity O(N) for the
model problem is presented here. In particular, the constant is 10. It is
much less than the constant for the optimal iterative approach, the mul-
tigrid method. That means a new record has been set. The parallelism in
this new algorithm allows an efficient parallel implementation. Generali-
zations of this algorithm are also discussed.
Another interesting fact is that this algorithm exhibits some concep-
tual connections with the new mathematical concept of fractals. In this
talk, we will demonstrate the rather interesting relations between the
optimal fast solver, template operators and fractals.
--
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