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 award-receiving dissertations will be published on line by the EATCS at http://www.eatcs.org/index.php/dissertation-award.
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 non-systematic data structures, the thesis shows that, quite surprisingly, with only 1 redundant bit it is possible to reply to queries in expected constant-time. 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 omega-regular tree languages or equivalently the languages defined by formulas of Monadic Second Order logic with several successors. The thesis makes progress on long-standing open problems in the theory of automata: the characterizations of regular languages of infinite trees that are definable in weak monadic second-order logic and the Rabin-Mostowski index problem. For both problems, Skrzypczak's thesis provides solutions for notable special cases.
Wootters' thesis approaches coding-theoretic 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 constant-sized alphabets, are optimally list-decodable (this answers a question asked by Elias over twenty years ago) and that there exist Reed-Solomon codes which are list-decodable 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 high-rate codes with local correctability that admits a sublinear-time 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.