A paper based on three Bachelor's theses from UvA Artificial Intelligence students has received the Best Paper Award at the IARIA 2018 Data Analytics Conference. The theses were written by Gijs van Horn, Richard Olij and Joeri Sleegers; their supervisor was Daan van den Berg of the Informatics Institute.
The paper is an extended replication of a study from the early 90’s. It shows that the average degree of an undirected graph can be used to predict the run time of a 'complete' algorithm. By extending the study with two more complete algorithms on the same input data, results suggest that algorithmic hardness might be a property of an instance itself, rather than of the specific algorithm deployed to solve it.
'The next step is to see whether these results hold for all known complete algorithms,' says Daan van den Berg. 'It might shine some light on the fundamentals of the exponential time hypothesis. But there are some problems too; speed can often increase at the expense of memory, and algorithms that are fast by one measure, can be slow by another.'
He continues: 'I am really happy with the award. The students invested a lot of free time, and it takes a lot of character to write a paper during the summer holidays. But luckily we were successful, and the hard work paid off.'