Saturday, April 25, 2015

EATCS honours three outstanding PhD theses with the first EATCS Distinguished Dissertation Awards

The 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

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.

ICTAC goes to Cali, Colombia

The organizing committee of ICTAC 2015 has asked me to help them distribute the following CfP of the event. The International Colloquium on Theoretical Aspects of Computing (ICTAC) is going to Colombia this year. The list of invited speakers is superb and Colombia has been a good source of young talent in TCS in recent years. Consider supporting this event by submitting a paper to it.

               CALL FOR PAPERS -- ICTAC 2015
                 12th International Colloquium on 
                 Theoretical Aspects of Computing
               29-31 October 2015, Cali, Colombia
                      ** **


ICTAC 2015 will take place at the campus of Universidad Javeriana, Cali, Colombia during October 29-31, 2015.  The ICTAC conference series aims at bringing together practitioners and researchers to exchange ideas and experiences addressing challenges in theoretical aspects of computing as well as in exploiting theory through methods and tools for system development.  ICTAC also aims to promote cooperation between participants and institutions from developing and industrial countries in research and education.

Topics of interest include theories of computation and programming, foundations of software engineering and formal techniques in software design and verification, as well as  tools that support formal techniques for software modeling, system design and verification.

The topical areas of the conference include, but are not limited to
*     Automata theory and formal languages;
*     Principles and semantics of programming languages;
*     Theories of concurrency, mobility and reconfiguration;
*     Logics and their applications;
*     Software architectures, their models, refinement and verification;
*     Relationship between software requirements, models and code;
*     Program static and dynamic analysis and verification;
*     Software specification, refinement, verification and testing;
*     Model checking and theorem proving;
*     Models of object and component systems;
*     Coordination and feature interaction;
*     Integration of theories, formal methods and tools for engineering computing systems;
*     Service-oriented architectures: models and development methods;
*     Models of concurrency, security, and mobility;
*     Theory of distributed, grid and cloud computing;
*     Real-time, embedded, hybrid and cyber-physical systems;
*     Type and category theory in computer science.

* Jean-Raymond Abrial
* Volker Diekert
* César Muñoz
* Catuscia Palamidessi
* Davide Sangiorgi
* Moshe Vardi
* Glynn Winskel

* ICTAC Summer School on Formal Methods (October 25-27)
* DCM 2015: 11th International Workshop on Developments in Computational Models (October 28)

== Important Dates 
* Abstract submission: Monday, June 1, 2015.
* Paper submission:   Friday, June 5, 2015.
* Author notification:  Monday, July 20, 2015.
* Camera ready:  Monday, August 3, 2015.

Thursday, April 02, 2015

CONCUR 2015 Deadline approaching

The deadline for CONCUR 2015 is approaching fast:
  • Submission of Abstracts: April 13th, 2015;
  • Submission of Papers: April 20th, 2015 (firm).
Note that you can submit your abstracts at any time before April 20. 

The usage of pdflatex and the LIPIcs style file are mandatory: no changes to font size, page geometry, etc. are permitted. Authors are invited to submit a draft of at most 13 pages including references. Submissions not in the correct format or submitted after the deadline will not be considered.