-By Francesca Serra
Lukas Larisch, a KAUST Ph.D. student in Computer Science working under the supervision of Professor Gabriel Wittum, won the PACE 2017 Parameterized Algorithms and Computational Experiments Challenge. The award ceremony that took place in Vienna, Austria, at the beginning of September this year has been held during the ALGO Congress at the International Symposium on Parameterized and Exact Computation (IPEC 2017).
Larisch shone in Track A of the PACE competition coming in first place in the Optimal Tree Decomposition Challenge where he won by solving more instances than competitors. He also got an honor position in the Heuristic Tree Decomposition Challenge.
A tree decomposition is a concept from Graph Structure Theory first introduced as a tool in the groundbreaking proof of the Graph Minor Theorem by Robertson and Seymour. On graphs of bounded treewidth, many NP-complete problems are solvable in polynomial time on optimal tree decompositions. The concept of tree decompositions is widely used in areas as Graph Structure Theory, Combinatorial Optimization, and Machine Learning.
"Parameterized Complexity is at the frontier of programming and algorithmic design because of its ability to isolate aspects, secondary measurements of the problems that are the cause of intractability. Secondary measurements beyond overall input size can crucially affect computational complexity both theoretically and empirically. Parameterized Complexity is well suited to the CEMSE goal of crossing borders with other scientific disciplines" said Frances Rosamond, Professor of Computer Science at the University of Bergen, and Chair of the PACE Challenge, "The results of this year were very impressive being two orders of magnitude faster than the ones of the previous editions. Lukas is a young star in the field of Parameterized Complexity."
Larisch earned his B.Sc. in Computer Science from the Goethe University of Frankfurt, Germany, with the thesis "Branch-width of Planar Graphs", in 2016. In the same year, he took part in the PACE 2016 program committee. After some time spent at the University of Leeds, United Kingdom, as a Research Scientist, he moved to the King Abdullah University of Science and Technology to pursue a Ph.D. and work in the Extreme Computing Research Center.
Despite his excellent results in graph theory, Larisch's true passion is classical music and the mathematical harmony that regulates musical instruments. "For my Ph.D. thesis, I want to continue research on understanding how musical instruments work as Pythagoras did, who is regarded as the first mathematician by ancient tradition. For this very purpose, we are creating a laboratory dedicated to musical acoustics here at KAUST. "Lukas said, "Besides my work in acoustics, I will continue my research in graph structure theory as well as my work on implementations of free and open-source libraries."
