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