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.