DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                    UNIVERSITY OF SOUTHERN DENMARK, ODENSE                   

                               Diagonalization                               

                                Lance Fortnow                                
                            NEC Research Institute                           

                      Thursday, May 11, 2000, at 2:15 PM                     
                               The Seminar Room                              


This talk will give a history and philosophy of diagonalization as a tool to
prove lower  bounds  in  computational  complexity.  We  will  give  several
examples and discuss  four possible approaches  to using  diagonalization to
separate log-space from nondeterministic polynomial-time.


                                                       Host: Kim Skak Larsen