Susanna de Rezende has been working as an associate senior lecturer in Algorithms and Complexity at the Department of Computer Science, Lund University, since December 2021. Today, the happy news arrived: She got an ERC Starting Grant for her project META, Meta-Computational Perspectives on Proof Complexity.
What does an ERC Starting Grant mean to you?
“It’s a game changer. It gives me the freedom to pursue an ambitious, long-term, high-risk, high-gain project, and to build a dedicated team of PhD students and postdoctoral researchers working exclusively on this project. I’m very grateful for the opportunity!” says Susanna de Rezende.
Can you tell me a little about the project?
“One of the big questions in computer science is to understand how hard different problems are for computers to solve. Some problems can be solved very quickly, while for others we do not know any efficient algorithm. Computational complexity theory tries to understand this difference: what are the possibilities and the limits of computation?
“But there is a second, deeper question. Sometimes we believe that a problem is hard because nobody has found an efficient algorithm. But we also cannot prove that no efficient algorithm exists. My project asks why this happens. Why is it so difficult not only to solve certain problems, but also to prove that they are hard?”
What do you hope to achieve?
“This project takes a step back and looks at the methods we use to prove that problems are hard. I want to understand the power and the limitations of these methods. When do they work? When do they fail? And can we explain why?
“There has been a lot of progress on these kinds of questions in the study of computational models called circuits. My project brings this meta-level perspective to the field of proof complexity, which studies the length and structure of mathematical proofs. In simple terms, I want to understand the limits not only of computation, but also of our ability to reason about computation.”
What kind of problems can it be about?
“There is a wide range of problems that can be modelled mathematically. For example, scheduling flights, planning routes, allocating resources, or organising snow removal can all involve many variables and many constraints. We may want to find the most efficient solution, but as the number of variables and constraints grows, this problem can become extremely difficult.
“My project is not about solving one specific scheduling or routing problem. Instead, it studies the mathematical foundations behind why some computational problems are hard, and why it can be so difficult to prove that hardness rigorously.”
Some current technologies are based on the assumption that certain problems are difficult for computers to solve efficiently, including encryption systems used in e-commerce and online banking.
“For some of these problems, we do not know any fast algorithm, but we also cannot prove that no fast algorithm exists. Still, modern cryptography often relies on the assumption that these problems are hard. If someone discovered a much faster algorithm, it could have major consequences for the security systems we use today.”
Susanna de Rezende’s profile in Lund University Research Portal