Wednesday, June 24, 2015

Program for ICALP/LICS 2015

ICALP/LICS 2015 is approaching fast and the very final version of the program for this event is available here.

A look at the program indicates the very broad coverage of TCS provided by the event. Apart from the presentation of 204 contributed papers (143 for ICALP and 61 for LICS), we will be treated to the following plenary invited talks:

Ken-ichi Kawarabayashi (NII, Japan)
Title: Digraphs Structures: Minors and Algorithms

Daniel Kifer (Pennsylvania State University, USA)
Title: Privacy and the Price of Data

Valerie King (University of Victoria, Canada)
Title: Dynamic Graphs: Time, Space, and Communication

Thomas Moscibroda (Microsoft Research and Tsinghua University, China)
Title: Incentive Networks

Anca Muscholl (Université Bordeaux, France)
Title: Automated Synthesis of Distributed Controllers

Peter O'Hearn (Facebook and University College London, UK)
Title: From Categorical Logic to Facebook Engineering

Luke Ong (University of Oxford, UK)
Title: Higher-Order Model Checking: An Overview

ICALP/LICS will also feature the following three tutorials:

Piotr Indyk (MIT, USA)
Title: Fast Algorithms for Structured Sparsity

Andrew Pitts (University of Cambridge, UK)
Title: Names and Symmetry in Computer Science

Geoffrey Smith (Florida International University, USA)
Title: Recent Developments in Quantitative Information Flow

as well as a "masterclass" on Algorithms and Complexity for Japanese Puzzles by
Ryuhei Uehara (JAIST, Japan).

The joint award session  will feature presentations by Xi Chen (Presburger Award recipient), Christos Papdimitriou (EATCS Award recipient) and Igor Walukiewicz (LICS Test-of-Time award recipient). Christos will also reflect on 40 years of theoretical computer science during a special anniversary event devoted to the 40th birthday of the journal Theoretical Computer Science.

Note that ICALP 2015 and LICS 2015 are truly co-located events. The two conferences will take place in the same week and at the same location. There is only one registration fee and conference participants will be able to attend whatever session they fancy at either conference.

I look forward to this festival of TCS and hope to have enough energy to report on some of the events on this blog. (I am still looking for guest bloggers!)

Friday, June 19, 2015

Call for guest posts from ICALP 2015/LICS 2015

If you are going to ICALP 2015/LICS 2015 and you are willing to contribute guests posts on that conference on this blog, drop me a line.

It would be good to have reports on the three tracks of ICALP, on LICS, on the invited talks/tutorials and on the award-related events, as well as on the conference as a whole.

In case you are interested, the guests posts on ICALP 2014 contributed by Clément Canonne and Andrew Winslow are here.

Tuesday, May 19, 2015

PhD positions in Computer Science at IMT Lucca (Italy)

This is the time of the year when IMT Lucca announces a number of fully funded PhD scholarships. IMT Lucca is one of the institutions in Italy that is closest to my heart and where I have had the pleasure to spend some time in the past interacting with PhD students and faculty. It provides an excellent environment for PhD students in a truly splendid setting. I strongly recommend it, if you are considering a PhD in several areas of computer science and control theory. Watch the video below, which will whet your appetite, and then read on.

The Institute for Advanced Studies IMT Lucca - Italy invites applications for fully-funded PhD scholarships in Computer Science tenable from 1st November 2015.

IMT Lucca is a truly international research university within the Italian public higher education system that focuses on cutting-edge research in key areas such as Computer Sciences, Systems Engineering, Complex Networks, Economics and Cultural Heritage. The three-year doctoral program, which is taught entirely in English, is articulated in four discipline-specific curricula that share an interdisciplinary scientific background.

Computer Science doctoral studies at IMT are coordinated by Rocco De Nicola and promote research on the theory and applications of informatics such as concurrency, performance, programming languages, security, dependability, software engineering, and computational biology. The overarching goal is to develop languages, models, algorithms, verification techniques, engineering methodologies, and software tools for reasoning about distributed systems.

The doctoral students will be working within the SysMA research unit of IMT Lucca (; some of the research lines are pursued in collaboration with two institutes of the Italian Research Council (CNR) in Pisa, namely ISTI ( and IIT (

PhD students receive a stipend of about €13,600 EUR gross (around €12,400 EUR after taxes) per year, as established by Italian law. In addition, they are offered free meals and on-campus housing in the historical center of the beautiful Tuscan city of Lucca. Students also get the opportunity to spend research periods abroad, with the possibility of receiving additional financing through the Erasmus+ program.

The deadline for application is June 29th, 2015 at 18:00 Italian time.

The call is open to all candidates who are expected to obtain the required degree by October 31st, 2015; however, they must still apply by the above deadline. Further details, along with the online application form, can be found at:

Saturday, May 02, 2015

ICALP 2015: Accepted papers and best paper awards

The PCs for the three tracks of ICALP 2015 have selected the best papers and best student papers. The best paper awards will go to the following articles:
  • Aaron Bernstein and Clifford Stein. Fully Dynamic Matching in Bipartite Graphs. (Track A)
  • Jarkko Kari and Michal Szabados. An Algebraic Geometric Approach to Nivat's Conjecture. (Track B)
  • Yiannis Giannakopoulos and Elias Koutsoupias. Selling two goods optimally. (Track C)
The best student papers will instead go to
As you can see Track A selected two best student papers, whereas Track C did not select any. Let me remark that Radu Curticapean already received the best student paper award at ICALP 2013.

The full list of accepted papers for each of the tracks of ICALP 2015 is here

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.

Tuesday, March 31, 2015

Ode to the Automata Tutor

I am slowly emerging from teaching a first year course on topics in Discrete Mathematics to about 250 students at Reykjavik University. (I have one more lecture to deliver after Easter and then the not-so-small matter of over 200 exam papers to grade :-() This is the second discrete mathematics course the students take and it is the second spring semester in a row that I teach it.

As part of the course, I am supposed to cover  the basics of grammars, finite automata and regular expressions. This is a first year course, so I do not cover much of the theory related to these formalisms and their connections. Mostly I expect the students to be able to design grammars, finite automata and regular expressions for some relatively simple languages.

In both editions of my course, which has been followed by about 500 students overall, I have used the AutomataTutor to support my teaching of material related to finite automata and to grade student assignments automatically.

For what it is worth, I strongly encourage my readers to try the tool and to use it in their undergraduate courses. In my experience, the students love to learn DFA and NFA programming using the Automata Tutor and to work on assignments that employ it. The automatic feedback and grading provided by the Automata Tutor are almost magical. (See this paper for a description of how the tool does both.) This is how the construction of finite automata that recognize regular languages should be taught in a modern way! I wish I had similar tools for all the topics I need to cover in that course.

From my perspective (and from that of my TAs), automatic grading is a real bonus. I love to teach, but I really hate to grade a large number of student assignments. Students can be very creative in their solutions and grading them is a very time consuming, haphazard and inconsistent process for any human. The algorithms embodied in the Automata Tutor produce consistent results at the press of a button and the students receive a grade straight away as well as excellent hints on how to improve incorrect solutions.

Thanks to Rajeev Alur, Loris D'Antoni, Sumit Gulwani, Dileep Kini, Mahesh Viswanathan and their co-workers, teaching basic finite-automata theory to hordes of first-year students can now (largely :-)) be done without tears. To boot, the folks at Automata Tutor have always been ready to provide technical help, when that was needed.

I'll keep using the Automata Tutor in my courses and I hope that you will do so too. That is the best way to thank our colleagues for the work they have done and are still doing on that tool.