Sixth edition of the VCLA International Student Awards 2021

Posted by on Tuesday, August 3, 2021 · Leave a Comment 

The highly successful sixth edition of the VCLA International Student Awards 2021 was concluded in July 2021. Out of the numerous submissions, one was selected for the Outstanding Master Thesis Award and one for the Outstanding Undergraduate Research Award by a committee consisting of eighteen internationally recognized researchers. The winner’s degrees have been awarded between November 15th, 2019 and December 31st, 2020 (inclusive).

 

Outstanding Master Thesis Award

Tuukka Korhonen (University of Helsinki) for the master thesis “Finding Optimal Tree Decompositions” under the supervision of Matti Järvisalo.

Abstract

The task of organizing a given graph into a structure called a tree decomposition
is highly relevant to databases and artificial intelligence. In particular, many
problems in these areas that are intractable in general become tractable if a suitable tree
decomposition of a graph describing the problem instance is given as a part of the
input. The running times of such algorithms depend on the quality of the given tree
decomposition, so this motivates the task of finding optimal tree decompositions.

In this thesis we consider the problem of finding an optimal tree decomposition
with respect to several different notions of optimality. Especially, we consider a
total of seven problems that are formulated as finding optimal tree decompositions:
treewidth, minimum fill-in, generalized and fractional hypertreewidth, total table
size, phylogenetic character compatibility, and treelength. Especially, the notions
of generalized and fractional hypertreewidth are highly relevant to tractability of
conjunctive queries in databases, and the notion of total table size is designed for
fine-grained optimization of tree decompositions for Bayesian inference.

In particular, we focus on the BT algorithm of Bouchitt´e and Todinca as a method
for finding optimal tree decompositions. The BT algorithm is well-known on the
theoretical side, but to our knowledge the first time it was implemented was only recently
for the 2nd Parameterized Algorithms and Computational Experiments
Challenge (PACE 2017). The author’s implementation of the BT algorithm took the second
place in the minimum fill-in track of PACE 2017. In this thesis we adapt and
implement the BT algorithm for each of the seven problems considered, achieving
state-of-the-art performance in several of them. We also contribute novel theoretical
analysis of the algorithm.

Download the thesis here (PDF)

Outstanding Undergraduate Thesis Award

Jasper Slusallek (Saarland University) for the undergraduate thesis “Algorithms and Lower Bounds for Finding (Exact-Weight) Subgraphs of Bounded Treewidth” under the supervision of Karl Bringmann.

Abstract

The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph is of bounded treewidth, as occurs in a variety of applications. Of particular interest to us is a weighted variant where the solution subgraph must be of total weight zero. Allowing the largest absolute weight to appear in the running time, we design new algorithms and show essentially matching lower bounds.

The conditional lower bounds are shown via a reduction from hyperclique. We achieve this by encoding some percentage of the hyperclique instance in the edges of the host graph, while encoding the rest in the weights. By setting the percentage that is stored in the edges to either of the extremes, we also show conditional lower bounds for the unweighted variant of the problem, as well as for Subset Sum.

On the algorithmic side, we first analyze the unweighted variant and use so-called k-wise matrix products to unify existing algorithms with a single technique, while still matching their running times. We then expand the algorithms to the weighted variant, improving on the best-known naive dynamic programming algorithm.

We also show similar results for the case of bounded pathwidth, with slight algorithmic improvements for both the weighted and the unweighted case. In this setting, we also show still further improvements for the node-weighted case.

Download the thesis here (PDF)

Awards

  • The Outstanding Master Thesis Award is accompanied by a prize of € 1200.
  • The Outstanding Undergraduate Thesis Award is accompanied by a prize of € 800.
  • The winners will be invited to the award ceremony, depending on the current COVID-19 situation.
  • The winners shall have the opportunity to present their theses.

The annually awarded VCLA International Student Awards acknowledge Bachelor and Master works that ask innovative questions and meet the highest academic standards for scientific research in the field of Logic and Computer Science. The awards are dedicated to the memory of Helmut Veith, the brilliant computer scientist who tragically passed away in March 2016, and aims to carry on his commitment to promoting young talent and promising researchers in these areas. See the current call for Helmut Veith Stipend for Female Master´s Students in Computer Science here.

 

VCLA Award Committee 2021

 

Previous Editions and Former Winners

Filed under Uncategorized · Tagged with

Comments are closed.