EATCS honours three outstanding PhD theses with the first EATCS Distinguished Dissertation Awards
EATCS is proud to announce that, after examining the nominations received from our research community, the EATCS Distinguished Dissertation Award Committee 2015, consisting of Javier Esparza, Fedor Fomin, Luke Ong and Giuseppe Persiano (chair), has selected the following three theses for the EATCS Distinguished Dissertation Award for 2015:
Each of the awards carries a monetary prize of 1000 Euros, provided by the EATCS. Each of the awardreceiving dissertations will be published on line by the EATCS at http://www.eatcs.org/index.php/dissertationaward.
Karl Bringmann's thesis consists of two parts: one dealing with ``Sampling from Discrete Distributions'' and one dealing with ``Computing Fréchet Distances.'' Sampling from a discrete probability distribution is a fundamental and classically studied problem. Bringmann's thesis contributes a deeper understanding of the amount of memory needed for sampling from a discrete probability distribution. The provided bound is tight for systematic data structures and for nonsystematic data structures, the thesis shows that, quite surprisingly, with only 1 redundant bit it is possible to reply to queries in expected constanttime. In the second part of the thesis, Bringmann relates the computational complexity of computing the Frechet distance of two curves (a classical notion from Computational Geometry) with a variant, SETH', of the Strong Exponential Time Hypothesis. Specifically, if SETH' holds, then the Frechet distance of two curves cannot be computed in time strongly subquadratic.
Skrzypczak’s thesis is about the use of descriptive set theory as a framework for investigating the omegaregular tree languages or equivalently the languages defined by formulas of Monadic Second Order logic with several successors. The thesis makes progress on longstanding open problems in the theory of automata: the characterizations of regular languages of infinite trees that are definable in weak monadic secondorder logic and the RabinMostowski index problem. For both problems, Skrzypczak's thesis provides solutions for notable special cases.
Wootters' thesis approaches codingtheoretic problems from an analytic point of view, rather than an algebraic point of view and develops new tools for studying codes, makes several contributions and settles a few important open problems. Specifically, Wootters' thesis advances the understanding of two important topics in Coding Theory: List Decoding and Local Seconding. Regarding List Decoding, the thesis shows that random linear codes, over constantsized alphabets, are optimally listdecodable (this answers a question asked by Elias over twenty years ago) and that there exist ReedSolomon codes which are listdecodable beyond the Johnson bound (this answers a question asked by Guruswami and Sudan over 15 years ago). Regarding Local Decoding, the thesis gives a family of highrate codes with local correctability that admits a sublineartime decoding algorithm.
The award committee received an impressive set of submissions in terms of quality. The three selected theses are outstanding and set very high standards for the future of this award, which is presented for the first time this year.
