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 (http://sysma.lab.imtlucca.it/); some of the research lines are pursued in collaboration with two institutes of the Italian Research Council (CNR) in Pisa, namely ISTI (http://www.isti.cnr.it) and IIT (http://www.iit.cnr.it).

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: http://phd.imtlucca.it

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 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.

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
                      ** http://www.ictac2015.co **


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.

Tuesday, March 03, 2015

February 2015 issue of the Bulletin of the EATCS on line

Thanks to the work of Kazuo Iwama, editor in chief of the bulletin, and of his collaborators, the February 2015 issue of the Bulletin of the EATCS is now available on line. You can download the whole issue in PDF from here, if you prefer. As a service to the TCS community, the bulletin continues being open access because of the support of the members of the EATCS, whom I thank wholeheartedly.

Amongst other things, this issue contains contributions by David Eppstein on K-Best Enumeration, Vikraman Arvind on Robust Oracle Machines revisited, Gaudi Taubenfeld on A Closer Look at Concurrent Data Structures and Algorithms (pages 59-82 of the whole issue), Jukka Suomela on Local Coordination and Symmetry Breaking ((pages 83-110 of the whole issue), Andreas Blass on Negative Probability and by Juraj Hromkovic who kicks off the new-look Education Column with a piece entitled Homo Informaticus.

I welcome Stefan Schmid as new editor of the Distributed Computing Column and thank Panagiota Fatourou for her sterling editorial work over many years.

Enjoy it. 

Monday, March 02, 2015

Video made by the female CS student association at Reykjavik University

I learnt a few things about some of the students taking the first-year course I am teaching right now by watching this well-made video.