Vienna Center for Logic and AlgorithmsWe are proud to announce the winners of the 2015 edition of the VCLA International Student Awards, and invite you to the prize ceremony that will take place on

Saturday, April 16, 16:30 to 18:00

in the Zeichensaal 3, Freihaus building of TU Wien

located in green area, 7th floor (map), Wiedner Hauptstraße 8-10, 1040 Vienna (map).


16:30 Welcome words Prof. Stefan Szeider, Vienna Centre for Logic and Algorithms
16:40 Presentation of the awardees Outstanding Undergraduate Research Award awarded to Felix Dörre (Karlsruhe Institute of Technology)
Outstanding Master Thesis Award awarded to Valeria Vignudelli (University of Bologna), presented
Honourable Mention (Master Thesis) awarded to Maximilian Schleich (Oxford University), presented
Talks by the awardees
17:00 Valeria Vignudelli The Discriminating Power of Higher-Order Languages: A Process Algebraic Approach [toggle name=”CV” linktext=”view CV”] Valeria Vignudelli completed her Master studies in 2013 at the Department of Philosophy of the University of Bologna, and she is currently enrolled as a third-year PhD student at the Department of Computer Science of the same university. The results presented in her Master thesis “The discriminating power of higher-order languages: a process algebraic approach”, written under the supervision of Giovanna Corsi and Davide Sangiorgi, are at the basis of the paper “On the discriminating power of passivation and higher-order interaction”, presented at CSL-LICS 2014 and co-authored with Marco Bernardo and Davide Sangiorgi. The thesis also won the 2014 Master thesis award by the Italian Association for Logic and Applications. Her PhD thesis is devoted to the study of behavioural equivalences for probabilistic higher-order languages, under the supervision of Davide Sangiorgi. She has co-authored papers accepted at QEST 2014 and POPL 2016, and she has been invited to present her work in international venues. Starting February 2016, Valeria is a visiting student at Inria Saclay in Paris, working with the Comète team led by Catuscia Palamidessi. [/toggle]  [toggle]Higher-order languages, whose paradigmatic example is the lambda-calculus, are languages with powerful operators that are capable of manipulating and exchange programs themselves. The theory of functional higher-order languages has been thoroughly studied, and higher-order languages for concurrent and distributed systems have been investigated as well. In this talk, I present a comparative study of the discriminating power of higher-order languages, based on a testing approach to behavioural equivalences on processes. The study is carried out by embedding first-order processes (the tested processes) in contexts of a higher-order language (playing the role of tests), and then examining the equivalence induced by the resulting contextual (or testing) equivalence on the first-order processes. In other words, the discriminating power of a language refers to the existence of appropriate contexts of the language that are capable of separating the behaviours of first-order processes. As tested first-order processes, embedded into the higher-order language, I consider both ordinary nondeterministic Labelled Transition Systems (processes that have multiple transitions with the same label) and reactive probabilistic Labelled Transition Systems (which exhibit probabilistic choices on transitions with the same label, thereby admitting no internal nondeterminism). The testing equivalences induced by the higher-order languages are characterised in terms of known behavioural equivalences on the two classes of first-order processes, and the expressiveness of higher-order operators emerges by comparing their interactions in the two settings.[/toggle]
17:20 Felix Dörre Verification of Random Number Generators [toggle name=”CV” linktext=”view CV”] Felix Dörre is an MSc student of Computer Science at the Karlsruhe Institute of Technology (KIT). His interests include formal methods for information security. Prior to starting his master studies, he received a BSc from KIT, with a thesis on verification of pseudorandom number generators (PRNGs). The deductive technique he developed is the first effective technical measure for quality assurance of cryptographic PRNGs.  Together with his advisor, Vladimir Klebanov, he published a first part of that work at the VSTTE 2015 conference. [/toggle]  [toggle name=”Abstract” linktext=”abstract”] This thesis presents the first quality assurance technique for pseudo-random number generator (PRNG) implementations. The developed logic-based verification tool is automatic and can be used by programmers with little or no formal methods training. The tool effectively detects such infamous defects as the Debian OpenSSL disaster or the Android PRNG vulnerability.[/toggle]
17:40 Maximilian Schleich Learning Regression Models over Factorised Joins [toggle name=”CV” linktext=”view CV”]Maximilian Schleich is a first-year PhD student in the database group in the Department of Computer Science at the University of Oxford. His research is at the interface of database systems and machine learning. He is investigating machine learning algorithms over large-scale databases, where his focus is on exploiting the structure of the machine learning input to avoid redundancy in data representation and computation. This approach complements common techniques to scale machine learning algorithms, such as distributing the data and computation. Prior to starting his PhD, Maximilian received the MSc in Computer Science from Oxford and a BSc in Computational Mathematics and Economics from The American University of Paris.[/toggle] [toggle]I investigate the problem of building least squares regression models over training datasets defined by arbitrary join queries on database tables. The key observation is that joins entail a high degree of redundancy in both computation and data representation, which is not required for the end-to-end solution to learning over joins.It is possible to use factorised representations of the join as input to regression models. The factorised join exploits laws of relational algebra, such as the distributivity of the Cartesian product over union, to reduce data and computation redundancy. The theoretical guarantees for the join size and computation time are well understood and are based on recent insights in the worst-case optimality guarantees for join queries. The size of the factorised join is governed by the fractional hypertree width, which is asymptotically optimal within the class of factorisations whose nesting structures are defined by the join hypergraph. In contrast, the corresponding bound of the flat representation of the join is based on the fractional edge cover. There exist classes of natural queries such as path, star, or hierarchical queries with the fractional edge cover number as large as the number of relations in the query and the fractional hypertree width one. There exists a worst-case optimal join algorithm which provides guarantees for the performance of the factorised join.The key contribution of this dissertation is to show that the worst-case bounds for factorised join computation can be extended to analytics when performed over joins of database tables. I present the linear regression learner F, which can learn the regression model in time linear in the size of the factorised join. All existing algorithms to compute linear regression models use the flat join as input and are, therefore, inherently suboptimal.F learns the parameters with a variant of the gradient descent optimisation algorithm. A rewriting of the least squares objective function decouples parameter convergence from computation dependent on the input data, by precomputing the cofactor for each parameter. All cofactors can be computed in only two passes over the factorised join, so that the entire regression model can be learned in two passes over the input data. Experimental results show that F needs orders-of-magnitude less memory and time to compute the parameters of the regression model with the same accuracy as competitors such as R or Python StatsModels.[/toggle]
The 2015 Award winners Maximilian Schleich, Felix Dörre, Valeria Vignudelli with Prof. Stefan Szeider

The 2015 Award winners Maximilian Schleich, Felix Dörre, Valeria Vignudelli with Prof. Stefan Szeider