The award ceremony for the winners of the 4th edition of the VCLA International Student Awards for Outstanding Bachelor and Master Theses took place on September 24, at 15:15. The award ceremony was collocated with the 9th Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2019).

This year´s awardees who have been invited to Vienna from Chile and Germany, were greeted by the vice rector for academic affairs of TU Wien, Kurt Matyas, and Prof. Gerti Kappel, who is going to take over the role of the dean of Faculty of Informatics in the autumn 2019. Following the ceremony, moderated by the chair of the VCLA Awards, Magdalena Ortiz, the winners gave a short presentation of their theses.

Outstanding Master Thesis Award is awarded to Martín Muñoz (Pontificia Universidad Católica de Chile) for the master thesis Descriptive Complexity for Counting Complexity Classes under the supervision of Marcelo Arenas and Cristian Riveros. Download the thesis here in PDF.

Abstract:

Descriptive Complexity has been very successful in characterizing complexity classes of decision problems in terms of the properties definable in some logics. However, descriptive complexity for counting complexity classes, such as FP and #P, has not been systematically studied, and it is not as developed as its decision counterpart. In this thesis, we propose a framework based on Weighted Logics to address this issue. Specifically, by focusing on the natural numbers we obtain a logic called Quantitative Second Order Logics (QSO), and show how some of its fragments can be used to capture fundamental counting complexity classes such as FP, #P and FPSPACE, among others. We also use QSO to define a hierarchy inside #P, identifying counting complexity classes with good closure and approximation properties, and which admit natural complete problems. Finally, we add recursion to QSO, and show how this extension naturally captures lower counting complexity classes such as #L.

Outstanding Undergraduate Thesis Award is awarded to Alexej Rotar (TU München) for the undergraduate thesis The Satisfiability Problem for Fragments of PCTL under the supervision of Jan Kretinsky. Download the thesis here in PDF.

Abstract:

The satisfiability of PCTL-formulae in general is a long standing open problem. Variations of the problem, such as the satisfiability of qualitative PCTL-formulae (Brázdil, Forejt, Kˇretínsk ` y, and Kucera, 2008), the bounded satisfiability (Bertrand, Fearnley, and Schewe, 2012), or the satisfiability for bounded PCTL-formulae (Chakraborty and Katoen, 2016) have been solved already. In this thesis, we tackle the satisfiability problem for various fragments of the quantitative PCTL. For this, we develop several techniques to reduce the size and complexity of models in order to obtain models of regular shape. Thereby, we show the small model property of the considered fragments. In particular, we prove that for those fragments, the general satisfiability problem and the finite satisfiability problem are equivalent. We also provide examples of obstacles for more general fragments. Besides the solutions presented in this thesis, the methods that we develop may serve as a framework to solve other fragments, as they are applicable to more general formulae.

VCLA International Student Awards

The annually awarded VCLA International Student Awards for Outstanding Undergraduate and Master Theses recognize and support students all over the world at the beginning of their scientific career in the field of logic in computer science. The awards entail an invitation to the award ceremony, and a cash prize fund of 2000 EUR. The VCLA Awards are dedicated to the memory of Helmut Veith, a brilliant computer scientist who tragically passed away in March 2016, and aim to carry on his commitment in promoting young talent and promising researchers in these areas.

Awards

• Outstanding Master Thesis Award:  1200 EUR
• Outstanding Undergraduate Research (Bachelor) Award:  800 EUR

VCLA Award Committee

New Call for Submissions

The deadline for submission of nominations for the degrees awarded between November 15th, 2018 and December 31st, 2019 (inclusive) is March 25, 2020.

Photo Gallery

Magdalena Ortiz, Kurt Matyas, Martin Munoz, Gerti Kappel	Magdalena Ortiz, Kurt Matyas, Alexej Rotar, Gerti Kappel	The VCLA Award committee with the winners of the VCLA International Student Awards 2019
Magdalena Ortiz, Chair of VCLA International Student Awards	Prof. Gerti Kappel, dean of the Faculty of Informatics of TU Wien	VCLA International Student Awards

Previous Editions and Former Winners

The third edition of the VCLA International Student Awards 2018

The second edition of the VCLA International Student Awards 2016

The first edition of the VCLA International Student Awards 2015