Surprising Symmetries for Theoretical Computer Science

In his search for fast algorithms, computer scientist Professor Michael Walter has come across surprising similarities: a wide range of research problems that appear to have little to do with each other can be traced back to symmetries and optimisation problems. This discovery offers a new perspective on well-known open questions in computer science and mathematics. Walter, who holds the Chair of Quantum Information at Ruhr-Universität Bochum (RUB), has been awarded a Starting Grant by the European Research Council (ERC) to pursue these connections. His ERC Starting Grant project “Symmetry and Optimization at the Frontiers of Computation” will start on 1 May 2022 and run for five years.

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 Cluster of Excellence "CASA - Cyber Security in the Age of Large-Scale Adversaries" and the Horst Görtz Institute for IT Security.

Press contact
Prof. Dr. Michael Walter
Chair of Quantum Information
Faculty of Computer Science
Ruhr-Universität Bochum
Germany
Phone: +49 234 32 25888
Email: michael.walter(at)rub.de

General note: In case of using gender-assigning attributes we include all those who consider themselves in this gender regardless of their own biological sex.