-------------------------------------------------------------------------------
                                       
                                       
                       B O S T O N   U N I V E R S I T Y
                                       
                          Computer Science Department
                                       
                              C O L L O Q U I U M
                                       
                              Friday May 13, 1994
                                       
                                    1:30pm
                          (Coffee served at 1:00pm)
                                       
                            Seminar Room / MCS 138
                                       

-------------------------------------------------------------------------------


        Utility of Incompressibility Arguments in Combinatorial Theory
                                       
                                 Paul Vitanyi
                       CWI & Universiteit van Amsterdam
                                       

                 We introduce the utility of incompressibility
                 (Kolmogorov complexity based)  arguments   in
                 combinatorial     theory by several  examples
                 (like the coin-weighing problem).  As another
                 example     we    explain    the     use   of
                 incompressibility to obtain the exact average
                 running    time  of  Heapsort,   due   to Ian
                 Munro. This is joint work with Ming Li.
                                       

                 Host: Prof. Steve Homer

-------------------------------------------------------------------------------
    For more information contact Prof. Azer Bestavros <bestavros@cs.bu.edu>
-------------------------------------------------------------------------------