Upgrading the toolkit for AI problems
FWF: What gaps in knowledge does your project aim to close? Robert Ganian: It is an essential task of theoretical computer science to understand which algorithmic problems can be solved efficiently in a step by step approach, under what conditions and how fast. Over the past 20 years, a paradigm for answering these questions has become established in computer science: parameterised complexity theory. It is a kind of toolkit for the analysis of classic problems in computer science, but one that you quite often cannot apply to current problems in artificial intelligence (AI) and machine learning (ML). To meet the challenges in this booming field, the toolkit must be modified appropriately. We need new tools, adjustments and extensions to understand under what conditions AI problems can be solved efficiently.
We cannot use the toolkit unthinkingly, but must find suitable starting points. In this context, fundamental knowledge lags behind applied results. Our project is designed to improve our understanding of why, when and how quickly AI and ML tasks can be solved. One typical area we want to explore is classification. Something that probably everyone knows is spam filters: an algorithm is expected to decide whether an email is a genuine message or spam. In the START project we want to develop an adapted toolkit based on parameterised complexity theory for typical problems in the areas of artificial intelligence and machine learning and establish a theory for it. FWF: What are the first steps? Ganian: We will start by analysing very carefully why the existing toolkit cannot be applied to certain problems. Next, we will revise it with a view to solving specific challenges. One major area we have in mind for adapting and extending the paradigm is sampling complexity. The second step is to apply the result to individual problems in the field of artificial intelligence, which is something you cannot do at the push of a button. We must produce specific evidence for each application. Our toolset will get us very accurate statements: on the one hand, we can use new algorithms to solve a problem in a given time; on the other, we can prove that there are no faster algorithms. In this way we will also test the limits of the method. FWF: What does the START Award mean for your research activities? Ganian: Trying to extend the theoretical framework to artificial intelligence is a really big endeavour, something I couldn't do on my own. In order to succeed, you need to bring together experts who are familiar with AI problem areas and experts like me who know the framework well. We have to work as a team to develop the adjustments and get them up and running. In other words we combine knowledge from different fields that one person alone cannot cover. FWF: What motivates you in your everyday research? Ganian: In my case it is a combination of several factors. At the most fundamental level, there is certainly my aspiration to understand how quickly and how well we can solve a problem. I am driven by the desire to answer this basic question. Another source of motivation is the fact that my research is also very interesting for many other people. My wife and my two children also inspire and motivate me. As researchers we have to be prepared to cope with failure. I always want to learn from my mistakes and do better next time.
Robert Ganian is a junior professor and a member of the Algorithms and Complexity Group at TU Wien (Vienna University of Technology). After his PhD from Masaryk University in Brno, Czech Republic, in 2012, he held a position at the Institute of Computer Science at Goethe University Frankfurt until 2013. His research focuses on parameterised algorithms and complexity theory. As of 2018, he has been conducting research on these topics within the framework of an FWF standalone project.
About the project The project “Parametrised Analysis in Artificial Intelligence” aims to upgrade an established theoretical computer science toolkit to make it usable for the booming applications of artificial intelligence (AI). Requirements in this context include new tools, the right approaches, extensions and an underpinning theory to understand under what conditions AI problems such as classification can be solved efficiently.
The START Prize The START programme of the Austrian Science Fund FWF is aimed at outstanding young researchers, giving them the opportunity to plan their research over an extended period and with a high degree of financial security. It is endowed with up to EUR 1.2 million and is one of Austria's most prestigious and most highly endowed awards alongside the Wittgenstein Award.