Surprising Symmetries for Theoretical Computer Science

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.

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 minimizing an objective function. The ERC project aims to explore these observations systematically.

The project starts in 2022.