Total search problems encompass computational tasks where solutions are guaranteed to exist. For instance, the problem of computing prime factorizations is total due to the fundamental law of arithmetic.
PhD defence, Thursday 31 August 2023, Kasper Høgh
During his Ph.D. studies, Kasper Høgh studied search problems where the existence of solutions follows from various topological existence theorems. Among other things, Kasper Høgh developed and applied novel techniques for studying the complexity of total search problems based on Brouwer's fixed point theorem.
The new research findings contribute to our understanding of the difficulty of computing equilibria in games and markets and fair divisions of resources in various settings.
The PhD study was completed at the Department of Computer Science, Faculty of Natural Sciences, Aarhus University.
This summary was prepared by the PhD student.
Time: Thursday, 31 August 2023 at 15:00
Place: Building 5342, room Ada-333, Department of Computer Science, Aarhus University, Åbogade 34, 8200 Aarhus N
Title of PhD thesis: Complexity of Total Search: Equilibria and Fair Division
Contact information: Kasper Høgh, e-mail: kh@cs.au.dk, tel.: +45 29 86 53 98
Members of the assessment committee:
Assistant Professor Ruta Mehta, Department of Computer Science, University of Illinois at Urbana-Champaign, USA
Senior Lecturer John Fearnley, Department of Computer Science, University of Liverpool, UK
Professor Ira Assent (chair), Department of Computer Science, Aarhus University, Denmark
Main supervisor:
Associate Professor Kristoffer Arnsfelt Hansen, Department of Computer Science, Aarhus University, Denmark
Language: The PhD dissertation will be defended in English
The defence is public.
The PhD thesis is available for reading at the Graduate School of Natural Sciences/GSNS,
Jens Baggesens Vej 53, building 5221, 8200 Aarhus N.