The 8th edition of the VCLA International Student Awards 2024 was concluded in September. Based on the international call for (self-)nominations, the award committee consisting of eighteen internationally recognized researchers announced one Outstanding Master Thesis Award and one Outstanding Undergraduate Research Award. As the decision on the Master Thesis Award was again a close call, there is also an honorary mention of a runner-up in this category. The nominated degrees had to be awarded between January 1, 2022 and December 31, 2023 (inclusive).

The Outstanding Master Thesis Award

The Outstanding Master Thesis Award goes to Tikhon Pshenitsyn (Lomonosov Moscow State University) for his master thesis “Hypergraph Lambek Calculus” under the supervision of Mati Pentus.

“I was interested in logical approaches to describing natural languages, so I decided to focus on formal grammars and substructural logics such as the Lambek calculus. I started working under the supervision of Mati Pentus when I was 17. I am thankful that he gave me full freedom to choose a research topic. After the second year, I learnt about graph grammars, which allow for the generation of graphs step-by-step using rules. I became interested in whether one could develop logic-based graph grammars similar to Lambek categorial grammars for strings. This resulted in an exciting research project I worked on for four years. Now, I believe that the hypergraph Lambek calculus is a mathematically sound formalism related to many approaches studied in the literature. Nicely, methods developed for this calculus helped me to answer an open question regarding commutative Lambek categorial grammars first asked by W. Buszkowski in 1984.”

Tikhon studies the Lambek calculus and related substructural logics, with a focus on algorithmic complexity. Currently, he’s interested in extensions of infinitary action logic by subexponential modalities; these logics have peculiar hyperarithmetical complexity. Another research interest are formal grammars, namely, type-logical categorial grammars and graph grammars. Recently, he became interested in biologically motivated formalisms in the formal language theory.

The English summary of his thesis is available here.

The Outstanding Master Thesis Award – Runner-up

There were many excellent submissions for the Outstanding Master Thesis Award, which is why we would like to give an honorary mention of the runner-up for winner in this category: Dieter Vandesande (Vrije Universiteit Brussel), master thesis “Towards Certified MaxSAT Solving: Certified MaxSAT Solving with SAT Oracles and Encodings of Pseudo-Boolean Constraints” under the supervision of Bart Bogaerts.

“I was introduced to the wonderful field of proof logging for combinatorial solvers in the course “Discrete Modelling, Optimization and Search”, where the goal of the exam project was to develop a MaxSAT solver that produces a proof in the VeriPB proof format. This is the key idea of proof logging: a combinatorial solver should not only produce an answer to its input problem, but also a proof of correctness of this answer. In the exam project, my teammate and I added proof logging to a rather old solver, namely QMaxSAT. My master thesis expands on the exam project by adding proof logging to two real-life MaxSAT solvers. On the one hand, I added proof logging to a newer version of QMaxSAT, focusing on proof logging the encoding of the model-improving constraint. On the other hand, together with my co-authors, we also added proof logging to the state-of-the-art core-guided MaxSAT solver CGSS, which is an extension of RC2, a well-known and robust state-of-the-art MaxSAT solver. “

Currently, Dieter is a PhD student under the supervision of Bart Bogaerts at the Vrije Universiteit Brussel. His main research interest is proof logging for a wide variety of combinatorial optimization solvers. Recently, he obtained a fellowship of the FWO Flanders for investigating proof logging in the context of Answer Set Programming.

A copy of his thesis is available here.

The Outstanding Undergraduate Thesis Award

The Outstanding Undergraduate Thesis Award goes to Nathaniel Collins (University of Colorado Boulder) for his bachelor thesis “Count-Free Weisfeiler–Leman and Group Isomorphism” under the supervision of Joshua A. Grochow.

“I was introduced to the Group Isomorphism problem and the Weisfeiler-Leman algorithm through my undergraduate advisors Michael Levet and Joshua Grochow. Michael was a teaching assistant in my undergraduate algorithms class. I came to his office hours and we started talking about complexity. The Weisfeiler-Leman algorithm is an interesting tool for group isomorphism as it is purely combinatorial yet it is able to capture many algebraic properties of groups. However, it is not known whether this algorithm solves the group isomorphism problem in polynomial time. Studying this algorithm on groups uses a lot of group theory, combinatorics, logic, and complexity theory which was a challenge to learn at the same time. However, it was very rewarding to see these different fields come together.”

Nate is now in his second year of a Master’s program in Mathematics at Colorado State University studying tensors. In particular, he’s interested in algebraic, geometric, and combinatorial properties of tensors which remain invariant under a change of basis.

A copy of his thesis is available here.

The VCLA International Student Awards

Helmut Veith, Co-Founder of VCLA

The annually awarded VCLA International Student Awards for Outstanding Undergraduate and Master Theses in Logic and Computer Science 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 (depending on the current COVID-19 situation) and a monetary prize from the fund of €2000. 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.

The VCLA Award Committee 2024

• Shqiponja Ahmetaj (chair)
• Michele Chiari
• Katalin Fazekas
• Daniela Kaufmann
• Matthias Lanzinger
• Xinghan Liu
• Anela Lolic (chair)
• Sanja Lukumbuzya
• Jan Maly
• Xavier Parent
• Vaidyanathan Peruvemba Ramaswamy
• Michael Rawson
• Martin Riener
• Sebastian Skritek
• Matteo Tesi
• Felix Winter
• Jules Wulms
• Kees van Berkel

The Former Awardees

• Lydia Blümel (University of Leipzig): Defining Defense in Abstract Argumentation from Scratch – A Generalizing Approach
• Barbora Šmahlíková (Brno University of Technology): Next Generation of Rank-Based Algorithms for Omega Automata
• Tuukka Korhonen (University of Helsinki): Finding Optimal Tree Decompositions
• Jasper Slusallek (Saarland University): Algorithms and Lower Bounds for Finding (Exact-Weight) Subgraphs of Bounded Treewidth
• Karolina Okrasa (Warsaw University of Technology): Complexity of variants of graph homomorphism problem in selected graph classes
• Antonin Callard (ENS Paris-Saclay): Topological analysis of represented spaces and computable maps, cb0 spaces and non-countably-based spaces
• Martín Muñoz (Pontificia Universidad Católica de Chile): Descriptive Complexity for Counting Complexity Classes
• Alexej Rotar (TU München): The Satisfiability Problem for Fragments of PCTL
• Tomáš Lamser (Masaryk University): Algorithmic Analysis of Patrolling Games
• Jeremy Liang An Kong (Imperial College London): MCMAS-Dynamic: Symbolic Model Checking Linear Dynamic Logic
• Felix Dörre (Karlsruhe Institute of Technology): Verification of Random Number Generators
• Valeria Vignudelli (University of Bologna): The Discriminating Power of Higher-Order Languages: A Process Algebraic Approach
• Maximilian Schleich (Oxford University): Learning Regression Models over Factorised Joins
• Pablo Muñoz (University of Chile): New Complexity Bounds for Evaluating CRPQs with Path Comparisons
• Kuldeep S. Meel (Rice University): Sampling Techniques for Boolean Satisfiability
• Luke Schaeffer (University of Waterloo): Deciding Properties of Automatic Sequences
• Sophie Spirkl (University of Bonn): Boolean Circuit Optimization

See the full list here