Susanna de Rezende has always been fond of mathematics. When she was in upper secondary school, she learned about Fibonacci numbers, a sequence of integers in which each new number is the sum of the two preceding ones. She began playing with the numbers in search of patterns, and found one. She felt very excited.

“It turned out I had found something that was already very well known. But I had still discovered it myself! I think that was where a spark was lit in me, a desire to become a researcher: perhaps it was also possible to discover things that no one knew yet…”

It took only a few years before she succeeded in doing just that, in a research project she participated in as a university student. Today she is a Wallenberg Academy Fellow at Lund University and conducts research on the limits of computer capabilities.

Computers can solve many problems much faster and more efficiently than humans. But they are not equally fast at all kinds of problems, and some things they seem unable to solve at all.

“When that happens, we often don’t know whether it’s simply because we haven’t found a way for computers to solve the problem, or whether the problem itself is actually hard for the computer. That’s what I am trying to find out,” says de Rezende.

Encryptions based on computer limitations

She is engaged in basic research, but her findings may have practical significance for encryption systems, which generally depend on there being things that computers are not good at. One example is RSA, an algorithm – a mathematical instruction for a computer – commonly used in modern encryption. RSA is based on multiplying large prime numbers, i.e., numbers that are divisible only by themselves and by 1. Only someone who knows or works out which two prime numbers were involved can crack the code. Even for a computer, it is extremely difficult to determine the two original numbers, based on the product – the number obtained by multiplication.

“This is a case where society acts as though it is impossible for computers to solve the problem. But actually we have no proof that this is so. It is also believed that if we manage to build large-scale quantum computers, they, unlike conventional computers, will be able to crack RSA encryption,” says de Rezende.

She does not work with quantum computers herself, but some of the problems she works on would probably be difficult even for quantum computers. This knowledge could therefore become valuable in preventing those computers from becoming a threat to security systems.

There are many problems we don’t want computers to be able to solve, such as breaking into our bank accounts. At present we act as though they were difficult to solve – but we have no proof of that.

Another class of problems that is difficult for computers to solve involves routes. A map app can quickly determine the shortest route between two locations. However, if we ask for the longest possible route that does not revisit any location, the problem becomes much harder.

“We believe that a computer actually needs to try all alternatives to provide the answer. It doesn’t do that to find the shortest path; instead, it has an algorithm, an efficient method of reasoning,” explains de Rezende.

No advanced technology needed

Not all algorithms “reason” in the same way; some have simpler models for their reasoning, others have more complex ones. Susanna de Rezende and her colleagues are studying algorithmic reasoning methods and attempting to demonstrate their limitations. If they can establish that a method is not efficient enough to solve a given problem, they will have identified a limit to computer capabilities. The practical work involves reading existing research, developing and testing ideas through logical reasoning, discussing with others, and ultimately formulating and proving precise results.

“Discussions are very helpful. Our research requires no advanced technology. A whiteboard and good pens are what we need,” says de Rezende.

She grew up in the Brazilian city of Campinas, not far from São Paulo. Both of her parents as well as her grandfather are mathematicians and researchers at the University of Campinas, her father in computer science and her mother and grandfather in mathematics.

“They understand some of what I do, but not all of it, because it’s so far removed from their own work. It’s interesting how within computer science and math you can have fields that are quite hard to understand even for mathematicians.”

Susanna de Rezende wanted to pursue her doctoral studies in Europe, preferably in Scandinavia. She visited several universities, including Lund, but at that time she felt that the theoretical computer science group there was a little too small. Nevertheless, she saw the potential and remembers thinking she would like to take up a position there later on and contribute to the growth of computer science. Meanwhile, she secured a doctoral position at KTH Royal Institute of Technology in Stockholm, where she was immediately attracted to one of the research teams. After a few years as a postdoc in Prague and a stint at the University of California, Berkeley, she wanted to return to Sweden. This time she came to Lund, where her field is now much larger and growing.

“We also collaborate extensively with the University of Copenhagen, which has strong groups in the same field. We have some very nice projects going on.”

Text Lisa Kirsebom
Translation Maxwell Arding
Photo Kennet Ruona