A plethora of questions
Credit: RUB, Marquard
A plethora of questions
The funded project falls within the realm of theoretical computer science. “Essentially, theoretical computer science is about finding fast algorithms and understanding structurally when such algorithms can’t exist,” explains Michael Walter. Starting point was a series of prior works in which, together with international colleagues, he noticed that several fundamental questions in a variety of fields might be connected, even though they seem to have nothing to do with each other at first glance.
“These include, for example, the question of whether random numbers can help us to calculate more quickly,” says Walter. “This is one of the fundamental open questions in computer science.” Other examples include the search for efficient estimation methods in statistics, as well as questions about the entanglement of quantum systems that are studied in the field of quantum information. The research also connects to variants of the P-vs-NP problem in theoretical computer science. “At its core, this is the question of whether it is really true that it is easier to verify the solution to a computational problem than to find the solution – which is supposedly something every child knows,” elaborates Walter. Further examples are so-called isomorphism problems in mathematics, which revolve around the question of when two geometric objects can be transformed into each other, and optimisation problems that occur in machine learning, for example, when calculating the similarity of two images.
A new perspective could be the key
All these problems have been studied by researchers in many communities for many years. “What we have now observed is – to put it simply – that symmetries are underlying all these questions,” describes Michael Walter. “Identifying these symmetries gives a new starting point for tackling these difficult questions.” In this case, the questions can often be phrased as optimisation problems that involve maximising or minimising an objective function. “This is quite unexpected, because most of the above questions seem to have nothing to do with optimisation at all,” says Walter. “Nevertheless we could already show in some special cases that the new perspective can be key to fast algorithms and new structural insights.”
Optimisation in curved spaces
The ERC project aims to explore these observations systematically. The optimisation problems that arise are theoretically not yet well understood. “This is because we are dealing with optimisation in curved spaces, whose properties are rather counterintuitive,” explains Michael Walter. “We hope to put the new optimisation paradigm on a solid theoretical foundation, develop universal methods, and apply the new approach to theoretical and practical problems such as those mentioned above. In particular, we hope to develop efficient numerical algorithms for challenging algebraic problems and to make progress on difficult questions in complexity theory, but also to find new applications for quantum computers. Overall, our goal is to achieve long-lasting insights across disciplines.”
About the person
Michael Walter studied mathematics and computer science at the universities of Karlsruhe and Göttingen, where he graduated in 2010 with a degree in mathematics. He subsequently obtained his doctorate from ETH Zurich, Switzerland, in 2014. From 2014 to 2017, he worked as a postdoctoral scholar at Stanford University, USA. He then joined the University of Amsterdam as an assistant professor. Since January 2022, Walter holds the Chair of Quantum Information at RUB. He is a member of the CASA Cluster of Excellence and the Horst Görtz Institute.
