Some computational problems can be solved quickly, while others remain extremely difficult even for today’s most powerful computers. During her PhD, Mette Marie Skjøtt Rasmussen studied so-called SAT problems, which are widely used both in theory to understand computational complexity and in practice to solve difficult combinatorial problems.

Her research focused on a random version of the SAT problem, and she showed that restricting parts of the input space leads to surprising probabilistic effects. These results reveal fundamental differences between different classes of instances, and can help explain why some problems are solvable, while others remain intractable.

This résumé is prepared by the PhD student.

Time: Friday 21 November at 09:00
Place: Building 1531, room 219 (Aud D4), Department of Mathematics, Ny Munkegade 118, Aarhus University, 8000 Aarhus C
Title of dissertation: Fixing variables in random satisfiability problems
Contact information: Mette Marie Skjøtt Rasmussen, e-mail: mette.marie.skjoett@gmail.com, tel.: + 45 41 25 17 44
Members of the assessment committee:
Professor Dimitris Achlioptas, Department of Informatics and Telecommunication,University of Athens, Greece
Associate Professor Albert H. Werner, Department of Mathematical Sciences, University of Copenhagen, Denmark
Associate Professor Markus Kiderlen (chair), Department of Mathematics, Aarhus University
University supervisor: Andreas Basse-O’Connor, Department of Mathematics, Aarhus University
Company supervisor: Allan Grønlund, Kvantify Aps.
Language: The PhD dissertation will be defended in English