Fourth Edition of the VCLA International Student Awards 2019

Posted by Mihaela Rozman on Friday, June 28, 2019 · Leave a Comment

VCLA International Student Awards 2019

The highly successful fourth edition of the VCLA International Student Awards 2019 was concluded on June 28, 2019. Out of 37 submissions in total, one was selected for the Outstanding Master Thesis Award and one for the Outstanding Undergraduate Research Award by a committee consisting of 19 internationally recognized researchers. The winner’s degrees have been awarded between November 15th, 2017 and December 31st, 2018 (inclusive).

NEW The deadline for submission of nominations for the VCLA International Student Awards 2020 – for the degrees awarded between November 15th, 2018 and December 31st, 2019 (inclusive) – is announced here.

Outstanding Master Thesis Award

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.

Magdalena Ortiz, Kurt Matyas (Vice-Rector for Academic Affairs), Martín Muñoz, Gerti Kappel.

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

Alexej Rotar (TU München) for the undergraduate thesis The Satisfiability Problem for Fragments of PCTL under the supervision of Jan Kretinsky.

Magdalena Ortiz, Kurt Matyas (Vice-Rector for Academic Affairs), Alexej Rotar, Gerti Kappel.

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.

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 have been invited to the award ceremony to Vienna.
The winners shall have the opportunity to present their theses in a digital format.

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.