wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (05/19/89)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY SEMINAR
-May 26, 1989
Dr. Robert Cori, University of Bordeaux, will speak on
"Partially abelian square free words."
TIME: 11:30 a.m.
ROOM: DC 1304
ABSTRACT
The notions of square-freeness and abelian
square-freeness of words are well known examples of
avoidable properties of words on sufficiently large
alphabets.
It is known since the beginning of the century
that square-free words exist on alphabets of
cardinality greater than 3, and answering to a question
of Erdos, Pleasants has shown in 1968 the existence of
abelian square free words of arbitrary length in a five
letter alphabet. The existence of such words on a 4
letter alphabet is still an open question.
The recent interest of theoretical computer
scientists for partially commutative free monoids
suggests the introduction of the notion of partially
abelian squares which generalizes these two notions.
One of the main results obtained concerns the
existence concerns the existence of arbitrary long
partially abelian square free words on a 4 letter
alphabet, when 4 among the 6 possible commutations
hold. Other results, mainly on enumeration, are given
in a three letter alphabet. In such an alphabet the
number of square free words of length n is known to be
greater than an exponential of n , it turns out that
the number of partially abelian square free words (when
only one commutation holds) is bounded by a polynomia
in n of degree 2.wlrush@water.waterloo.edu (Wenchantress Wench Wendall) (08/03/89)
Dartmouth University, will speak on
``Randomized Algorithms and Randomized Reductions in Number Theory.''
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY SEMINAR
-Friday, August 11, 1989
Professor Jeffrey Shallit, Dept. of Computer Science,
Dartmouth University, will speak on ``Randomized
Algorithms and Randomized Reductions in Number
Theory.''
TIME: 2:00 p.m.
ROOM: DC 1302
ABSTRACT
In this talk, I'll survey the role of the randomized
algorithm and the randomized reduction in proving
results in number-theoretic complexity.
Rabin and Solovay & Strassen first showed the utility
of randomized algorithms in proving numbers composite.
Many other problems in number theory, for which no fast
deterministic algorithm is known, turn out to be
solvable in random polynomial time. I'll discuss
several new examples, including Pollard's algorithm for
quadratic congruences, and representations as sums of
squares (joint work of Michael Rabin and myself).
Gary Miller showed the value of randomized reductions
in proving that certain functions from elementary
number theory are "hard". (By a "hard" problem I mean
one that is at least as hard as factoring. This is a
number-theoretic analogue of NP-hardness.) I'll show
that several classical problems, such as the Euler phi
function, and the sum of divisors function, fall into
this class. An amusing consequence is that there is a
BPP algorithm to tell if a number is perfect or
multiperfect. This is joint work with Gary Miller and
Eric Bach.
Finally, I'll discuss the relationship of these
reductions with the recent elliptic curve factoring
algorithm of Hendrik Lenstra.