clarke@utcsri.UUCP (Jim Clarke) (11/08/86)
(GB = Galbraith Building, 35 St. George Street)
(SF = Sandford Fleming Building, 10 King's College Road)
THEORY SEMINAR - Monday, November 17, 4 p.m. SF 1101
Professor Eugene Luks
Department of Computer & Information Sciences
University of Oregon
"Parallel Algorithms for Permutation Groups and Graph Isomorphism"
(see abstract below)
COLLOQUIUM - Tuesday, November 18, 11 a.m. SF 1101
Dr. Peter Borwein
Dalhousie University
"How to compute 100-million digits of Pi"
(see abstract below)
GRAPHS SEMINAR - Tuesday, November 18, 2 p.m. GB 120
Dr. Philip Barnard
MRC Applied Psychology Unit, Cambridge, England
"Approximate Modelling of Cognitive Activity:
Towards an Expert System Design Aid"
ARTIFICIAL INTELLIGENCE - Tuesday, November 18, 3 p.m. GB 119
Professor James Schmolze
Computer Science Department
Tufts University, Medford, Maryland
"Physics for Robots"
ABSTRACTS:
"Parallel Algorithms for Permutation Groups and Graph Isomorphism"
Professor Eugene Luks
We develop a machinery for fast parallel computation with permutation
groups. For a large class of groups (including those with bounded nona-
belian composition factors) this puts fundamental problems into NC. These
problems include: finding the order, membership-testing, finding the
center, finding (representing) the composition factors, and finding the
subgroup that fixes all the points in any subset. The latter is applied to
graph isomorphism and fast parallel algorithms are developed for testing
isomorphism of vertex-colored graphs with bounded color classes.
"How to Computer 100-Million Digits of Pi"
Professor Peter Borwein
We discuss what is probably the fastest known algorithm for pi, both
theoretically and practically. Thirteen iterations provide in excess of a
hundred million digits of pi. Related to the above is a quartic algorithm
for any elementary transcendental function.
The genesis of the above thoroughly non-obvious algorithm and associ-
ated computational concerns will be the primary focus of this talk. A
brief account of the long history of computing digits of pi, as well as a
discussion of the current state of our ignorance concerning computational
properties of irrationals, will also be included.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke