cfry@watdcsu.waterloo.edu (C.Fry - Inst. Computer Research) (03/23/88)
On Some Lower Bounds
by
Prof. Anna Lubiw
of
Department of Computer Science
University of Waterloo
Abstract
Everybody knows that sorting n numbers takes n log n comparisons.
In some sense this is true simply because the number of possible
outputs is so large (namely n!).
This talk will be about what happens when: (1) the model is made
stronger so that more than just comparisons are allowed; and (2)
the problem is made easier so that there are fewer possible out-
puts. The particular problem to be considered will be the ele-
ment distinctness problem: given n numbers, are they all dis-
tinct? This problem is so basic that lower bounds for it provide
lower bounds for many other problems (including sorting).
I will discuss Ben-Or's result that solving this problem for n
real numbers takes n log n steps on a model of computation which
generalizes comparison trees by allowing some arithmetic. This
result uses a theorem in algebraic geometry. Then I will discuss
work I have done with A. Racz on strengthening Ben-Or's results
to integer inputs.
DATE: March 30, 1988
TIME: 3:30 p.m.
PLACE: MC 3005 (Please note room change)
Everyone is welcome. Refreshments served.