Fifth edition of the VCLA International Student Awards 2020

Posted by on Tuesday, July 14, 2020 · Leave a Comment 

The highly successful fifth edition of the VCLA International Student Awards 2020 was concluded in July 2020. Out of 44 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 eighteen internationally recognized researchers. The winner’s degrees have been awarded between November 15th, 2018 and December 31st, 2019 (inclusive).

Outstanding Master Thesis Award

Karolina Okrasa (Warsaw University of Technology) for the master thesis “Complexity of variants of graph homomorphism problem in selected graph classes” under the supervision of Paweł Rzążewski.

Abstract

A homomorphism is a function which maps vertices of a graph G to vertices of a graph H in which each edge of G is mapped to some edge of H. For a xed graph H, by Hom(H) we denote the computational problem of deciding whether a given graph G admits a homomorphism to H. Graph homomorphisms are generalization of graphs colorings, as if H is a complete graph on k vertices, then Hom(Kk) is equivalent to k-coloring. A result of Hell and Ne²et°il states that if H is bipartite or has a vertex with a loop then Hom(H) is polynomial-time solvable and otherwise it is NP-complete.

In this thesis we consider complexity bounds of NP-complete cases of Hom(H), parameterized by the treewidth of the instance graph G. Using both algebraic and combinatorial tools, we show that for almost all graphs H the complexity obtained by a straightforward dynamic programming on a tree decomposition of G cannot be improved, unless the Strong Exponential Time Hypothesis (a standard assumption from the complexity theory) fails.

In the second part of the thesis, we analyse the cases of graphs H for which the bound obtained by the dynamic programming method can be improved. We prove another lower bound with an additional restriction on H and show that it is tight for all graphs H, if we assume two conjectures from algebraic graph theory. In particular, there are no known graphs H which are not covered by our result.

Download the thesis here (PDF)

 

Outstanding Undergraduate Thesis Award

Antonin Callard (ENS Paris-Saclay) for the undergraduate thesis “Topological analysis of represented spaces and computable maps, cb0 spaces and non-countably-based spaces” under the supervision of Mathieu Hoyrup.

Abstract

The aim of this thesis is to study the relationships between topology and computability on several classes of represented spaces. The case of countably-based (or cb0) spaces has been studied for a handful of years, but we still lack a general case for well-known theorems in subcases of the theory (like in Polish spaces). Additionally, scientists know very little of some other spaces (like the space of real polynomials R[X]), even though the possibility to algorithmically manipulate them would be truly desirable. My attempt here is to generalize results (which were already known in quasi-Polish spaces) to countablybased spaces, and to study whether we could envision extending notions of computability (and of Descriptive Set Theory) outside of their usual background, in the specific example of real polynomials.

In this document, I disclose three of the main results we have obtained:
• In countably-based spaces, the topological complexity of an effective set (ie. its position in the difference hierarchy) and its algorithmic complexity (ie. the complexity of its preimage under the representation) are equivalent. This is an effectivization of a result already known since.
• In countably-based spaces, it is equivalent for a map to be piecewise-computable with a countable cover, and for its “algorithmic realization” to also be piecewise-computable with a countable cover. We also generalize an already known counter-example in the finite case.
• On the space of real polynomials, we exhibit a set whose algorithmic complexity differs from its topological complexity. This implies that a representation cannot capture every topological phenomenon on R[X]. As a consequence, we demonstrate that the Wadge and the Hausdorff-Kuratowski theorems do not apply on this space.

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.
  • 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 2020

Previous Editions and Former Winners

Filed under Uncategorized · Tagged with

Comments are closed.