Structural Aspects of Computational Complexity: Class Separations and Reductions
Event details
| Date | 19.06.2025 |
| Hour | 12:30 › 14:30 |
| Speaker | Valentin Imbach |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Mika Göös
Co-examiner: Prof. Michael Kapralov
Abstract
This thesis investigates structural aspects of computational complexity, focusing on class separations and the role of reductions in understanding the relationships between complexity classes. Special attention is given to the class TFNP, which captures total function problems, and its significance in the broader landscape of search problems. We also examine constant cost classes, exploring how severely restricted computational models relate to more familiar complexity classes. Through the study of reductions and structural properties, this work aims to shed light on the underlying organization of computational problems and the boundaries of efficient computation.
Selected papers
1. Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
https://arxiv.org/pdf/2503.15294
2. How to fit large complexity classes into TFNP
https://arxiv.org/pdf/2412.09984
3. Unique End of Potential Line
https://arxiv.org/abs/1811.03841
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Mika Göös
Co-examiner: Prof. Michael Kapralov
Abstract
This thesis investigates structural aspects of computational complexity, focusing on class separations and the role of reductions in understanding the relationships between complexity classes. Special attention is given to the class TFNP, which captures total function problems, and its significance in the broader landscape of search problems. We also examine constant cost classes, exploring how severely restricted computational models relate to more familiar complexity classes. Through the study of reductions and structural properties, this work aims to shed light on the underlying organization of computational problems and the boundaries of efficient computation.
Selected papers
1. Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
https://arxiv.org/pdf/2503.15294
2. How to fit large complexity classes into TFNP
https://arxiv.org/pdf/2412.09984
3. Unique End of Potential Line
https://arxiv.org/abs/1811.03841
Practical information
- General public
- Free
Contact
- edic@epfl.ch