The START Prize is considered the most important Austrian award for young scientists. Its endowment of up to €1.2 million provides the necessary financial security to establish their research group at an internationally competitive level.

This year, Robert Ganian receives the START Prize for his project to build a bridge between complexity theory and artificial intelligence.

A Problematic Variety: The NP Problem

In informatics, a distinction is made between simple and complicated tasks: Adding up a long list of numbers is easy. If the computer has to add twice as many numbers, it takes about twice as long—that’s no problem. But what happens when a robot has to visit ten different places and has to calculate in which order it should go to them so that the path is as short as possible? This question is a so-called NP problem—and this is the problematic variety: If the next time there are not ten but twenty different targets, the calculation does not take twice as long, but much longer. The computing effort increases exponentially with the amount of data entered.

Robert Looks for Precise Characterization

The distinction between simpler P-problems and more difficult NP-problems has existed for a long time. Robert, however, is looking for ways to characterize the complexity of computational tasks more precisely at our Institute of Logic and Computation. Are there perhaps specific recurring patterns in the input data? Is it possible to use particular structures in an intelligent way to solve even difficult problems in an acceptable time?

The tools Robert is working on are already being used in various areas of IT. He also wants to bring these methods into the research field of artificial intelligence (AI): How can machines be made to learn something as efficiently as possible? How much input do they need? How large must the amount of data be for a computer to learn something from it in an intelligent way?

About Robert Ganian

Robert studied at Masaryk University in Brno, where he also completed his doctoral thesis in 2012. He then moved to the Goethe University in Frankfurt. Since 2013 he has been researching at TU Wien Informatics’ research unit Algorithms and Complexity, where he habilitated in 2019 and has already established a small research group as part of an FWF individual project.

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.