Campus Event Calendar
Event Entry
What and Who
Problems of Unknown Complexity: Graph isomorphism and Ramsey theoretic numbers
Pascal Schweitzer
Max-Planck-Institut für Informatik - D1
Promotionskolloquium
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 24 July 2009
16:00
90 Minutes
E1 4
024
Saarbrücken
Abstract
In my thesis I consider three computational problems with unknown complexity status: the graph isomorphism problem, the problem of computing van der Waerden numbers and the problem of computing Ramsey numbers. For each of the problems, an algorithm is devised and subsequently analyzed with theoretical and practical means by a comparison with contemporary algorithms that solve the respective problems.
In the talk, where I report on my thesis as part of my PhD defense, I will mainly focus on the ScrewBox algorithm which solves the graph isomorphism problem by a random sampling process. I will elaborate on its algorithmic design and functionality as well as on the theoretical and practical comparison that is performed.
Contact
Pascal Schweitzer
--email hidden
passcode not visible
logged in users only
Pascal Schweitzer, 07/14/2009 14:50 -- Created document.