[ont.events] ICR March 30 Prof Lubiw On Some Lower Bounds

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.