At long last, the EATCS has a YouTube channel. (Thanks to the EATCS Secretary office in Patras for setting it up and for making us enter the 21st century :-)) In due course, the videos of the invited talks and of the EATCS-Award-2013 presentation by Martin Dyer from ICALP 2013 will be available from that channel. For the moment, you can enjoy Erik Demaine's wonderful Presburger Award 2013 video.
Make sure that you subscribe to the channel to get updates on our postings.
The slides for Jon Kleinberg's inspiring EATCS lecture are available here.
Several people asked me for the slides and Jon agreed to make them public. Thanks Jon!
Conference photos taken at ICALP 2013 can be found here. Enjoy.
Tuesday, July 23, 2013
Thursday, July 18, 2013
CAV Award 2013
The CAV Award for 2013 has been presented to Kim G. Larsen, Paul Pettersson and Wang Yi for their seminal work on Uppaal, which is the foremost tool suite for the verification of real-time systems and the synthesis of real-time controllers. Congratulations to the awardees for receiving this well deserved accolade and to the award committee for making such an excellent choice!
If you are interested in using the tool for research and/or teaching, simply download it and read this tutorial by Frits Vaandrager. You will be up and running in no time.
Uppaal has its roots in a tool originally developed in Uppsala and described in the conference paper Automatic verification of real-time communicating systems by constraint-solving co-authored by Wang Yi, Paul Pettersson and Mads Daniels (Proceedings of FORTE 1994). Since then, Uppaal has been jointly developed by Kim G. Larsen's research group at Aalborg University and by the group led by Wang Yi at Uppsala University. In this period, Uppaal has become an industrial-strength tool for computer-aided verification of computing systems that has been applied to many case studies by several research groups in academia and industry. The efficiency of its computational engine has been improved greatly by theoretical and practical advances relying on highly non-trivial insights. Moreover, the tool now supports the analysis of quantitative extensions of timed automata, automatic model-based testing of real-time systems and the synthesis of controllers in the context of timed games. It is still under continuous development.
Overall, the Uppaal tool is a real success story for the research community working on automated verification of computer systems. As all long-term research and tool development efforts, the work on Uppaal and its applications is due to many gifted researchers and their students. The CAV Award 2013 cannot recognize them all, but the list of authors of the many papers stemming from the work on UPPAAL gives a hint of the magnitude of the research effort involved in building such a tool over a period of nearly 20 years.
If you are interested in using the tool for research and/or teaching, simply download it and read this tutorial by Frits Vaandrager. You will be up and running in no time.
Uppaal has its roots in a tool originally developed in Uppsala and described in the conference paper Automatic verification of real-time communicating systems by constraint-solving co-authored by Wang Yi, Paul Pettersson and Mads Daniels (Proceedings of FORTE 1994). Since then, Uppaal has been jointly developed by Kim G. Larsen's research group at Aalborg University and by the group led by Wang Yi at Uppsala University. In this period, Uppaal has become an industrial-strength tool for computer-aided verification of computing systems that has been applied to many case studies by several research groups in academia and industry. The efficiency of its computational engine has been improved greatly by theoretical and practical advances relying on highly non-trivial insights. Moreover, the tool now supports the analysis of quantitative extensions of timed automata, automatic model-based testing of real-time systems and the synthesis of controllers in the context of timed games. It is still under continuous development.
Overall, the Uppaal tool is a real success story for the research community working on automated verification of computer systems. As all long-term research and tool development efforts, the work on Uppaal and its applications is due to many gifted researchers and their students. The CAV Award 2013 cannot recognize them all, but the list of authors of the many papers stemming from the work on UPPAAL gives a hint of the magnitude of the research effort involved in building such a tool over a period of nearly 20 years.
Monday, July 15, 2013
ICALP 2013 (Part 3): Award sessions
The best paper award session at ICALP 2013 was held last Monday before the welcome reception (which included excellent, and plentiful, finger food and wine). Mark Bun, John Fearnley and Dominik Pajak
delivered very good presentations of the award-winning papers. I hope
that you will check out their papers. In the case of the paper by Mark
and Justin Thaler, you can also read this expository blog post.
The EATCS Award and the Presburger Award were delivered last Tuesday in a joint ceremony that also included the award of honorary doctorates to Josef Gruska and Juris Hartmanis. (See this earlier post of mine for some more information on the ceremony for the honorary doctorates.)
The master of ceremony for the award session was Paul Spirakis. First Martin Dyer received the EATCS Award from Friedhelm Meyer auf der Heide and delivered a presentation entitled Counting ain't easy. Martin started by citing the following fragment of a rhyme from the Winnie the Pooh books:
Cheers for Pooh!
(For who?)
For Pooh -
(Why, what did he do?)
I thought you knew
He then proceeded to give an accessible historical overview of what he did do, covering essentially all the work mentioned in the laudatio for the award.
Last, but by no means least, Tony Kucera presented the Presburger Award 2013 to Erik Demaine. Unfortunately, Erik could not be with us in Riga, but we had a virtual presentation of the award to him via Skype. Moreover, Erik produced an excellent video of a presentation that we could play and enjoy at the conference. Rather than attempting to summarize Erik's inspirational talk, I will simply limit myself to letting him speak for himself.
The EATCS Award and the Presburger Award were delivered last Tuesday in a joint ceremony that also included the award of honorary doctorates to Josef Gruska and Juris Hartmanis. (See this earlier post of mine for some more information on the ceremony for the honorary doctorates.)
The master of ceremony for the award session was Paul Spirakis. First Martin Dyer received the EATCS Award from Friedhelm Meyer auf der Heide and delivered a presentation entitled Counting ain't easy. Martin started by citing the following fragment of a rhyme from the Winnie the Pooh books:
Cheers for Pooh!
(For who?)
For Pooh -
(Why, what did he do?)
I thought you knew
He then proceeded to give an accessible historical overview of what he did do, covering essentially all the work mentioned in the laudatio for the award.
Last, but by no means least, Tony Kucera presented the Presburger Award 2013 to Erik Demaine. Unfortunately, Erik could not be with us in Riga, but we had a virtual presentation of the award to him via Skype. Moreover, Erik produced an excellent video of a presentation that we could play and enjoy at the conference. Rather than attempting to summarize Erik's inspirational talk, I will simply limit myself to letting him speak for himself.
Sunday, July 14, 2013
ICALP 2013 (Part 2): Invited talks
ICALP 2013 in Riga featured five invited presentations and a special EATCS lecture to celebrate the 40th edition of the ICALP conference.
The scientific program for the conference was preceded by short presentations by the rector of the University of Latvia and by Rusins Freivalds. The rector welcomed the ICALP participants, gave us some interesting information about the University of Latvia and wished us long coffee breaks. Rusins discussed the unity of science, and reminded us that, even at the time of the iron curtain, there was one Computer Science.
The conference proper was kicked off on Monday, 8 July, by an invited talk delivered by the Liverpool-bound Paul Spirakis. Paul's talk was entitled A Guided Tour in Random Intersection Graphs. Random Intersection Graphs are random graphs in which there is a universe M of labels and each one of the vertices selects a random subset of M. Two vertices are connected if, and only if, their corresponding subsets of labels intersect. Random intersection graphs were introduced by M. Karonski, E.R. Sheinerman and K.B. Singer-Cohen and have several applications, as well as a rich theory. Paul's talk provided a survey of the main results on the topic obtained by his research group on combinatorial problems over random intersection graphs, such as independent sets, Hamiltonian cycles, colouring, maximum cliques, expansion and random walks. Paul closed the talk by saying that this model is an excellent area of study for PhD students in TCS.
Tuesday's invited address was delivered by Daniel Marx. Daniel's talk has three chapters (his words) and was entitled The Square Root Phenomenon in Planar Graphs. Its starting point was the observation that most of the classic NP-hard problems remain NP-hard when restricted to planar graphs, and only exponential-time algorithms are known for the exact solution of these planar problems. However, in many cases, the exponential-time algorithms on planar graphs are significantly faster than the algorithms for general graphs: for various problems on planar graphs, one often sees a square root appearing in the exponent of the running time of the best algorithms for their solution. Daniel told his audience that, by now, we have a good understanding of why this square root appears: most of these algorithms rely on the notion of treewidth and its relation to grid minors in planar graphs. Daniel also argued that, under the Exponential Time Hypothesis, one can show that these algorithms are essentially best possible, and therefore the square root must appear in the running time.
In passing, Daniel contributed also one paper to ICALP Track A and one to ICALP Track B!
Susanne Albers delivered the invited talk on Wednesday, 10 July, on Recent Advances for a Classical Scheduling Problem. In her talk, Susanne revisited the classic on-line makespan minimization problem, which has been studied since the 1960s. After presenting the classic results on this problem, starting from Graham's 1966 List algorithm and its competitive analysis, she surveyed recent research on settings in which an online algorithm is given extra information or power while processing a job sequence.
The scientific programme on Thursday, 11 July, started with an invited talk by Orna Kupferman, who gave the only invited address that could be readily classified as belonging to ICALP Track B. Orna's presentation dealt with Formalizing and Reasoning about Quality. Traditionally, formal approaches to the verification of reactive systems are boolean in nature: either a system satisfies its specification or it doesn't. In case a system does not meet its specification, one expects a good verification framework to provide a counter-example, that is, a reason why the system is not correct. Orna and her co-authors have generalized formal specification and verification methods to address the quality of systems. In her talk, Orna introduced the linear temporal logic LTL[F], where F is a set arbitrary functions over the interval [0, 1]. Formulae in LTL[F] are interpreted over computations consisting of sequences of atomic propositions. The satisfaction value of an LTL[F] formula is a number between 0 and 1 that describes how well a computation satisfies a formula. The logic generalizes traditional LTL with the functions in F; examples of functions that might be in F are the maximum or minimum between the satisfaction values of subformulas (these are the quantitative counterparts of boolean OR and AND, respectively), their product and their average. In her talk, Orna showed us how to generalize classic decision problems in formal methods, such as satisfiability, model checking and synthesis, to search and optimization problems in the quantitative setting. This is achieved by means of an extension of the automata-theoretic approach to LTL to the setting of LTL[F].
Before the conference dinner, Jon Kleinberg delivered a special EATCS lecture to celebrate the 40th ICALP. Jon gave an inspiring and very articulate talk entitled Algorithms, Networks, and Social Phenomena. The talk discussed the development of computational models for systems involving social networks and large human audiences. In particular, Jon focused on how information spreads through such systems, and the ways in which this spread is affected by the underlying network structure. Jon said a few times that, despite having so much data at our disposal, we still do not understand human behaviour. However, IMHO, the work by Jon and his coworkers is shedding some light on some aspects of our behaviour.
Peter Widmayer delivered the last invited talk on Friday, 12 July. His presentation was entitled To Be Uncertain Is Uncomfortable, But to Be Certain Is Ridiculous, and was accessible and well paced. The starting point of Peter's talk was a "Socratic dialogue" between a statistical physicist and himself. Traditionally, in combinatorial optimization one assumes that an input instance is given with absolute certainty. The goal is then to find an optimum solution for the given instance. In contrast, as the statistical physicist would argue, input data are in reality uncertain, noisy and inaccurate. As a consequence, an optimum solution to a combinatorial optimization problem might not be meaningful in practice. (For example, the shortest path to our work place we computed yesterday evening might not be usable this morning because of changed traffic conditions.) Peter advocated the development of algorithms that find "meaningful" solutions in the presence of uncertain inputs, proposed an approach towards reaching this goal. and argued that it leads to good solutions in the real world.
Videos of these talks (with the exception of Kleinberg's talk, which, as far as I know, was not recorded) will be available in due course.
The scientific program for the conference was preceded by short presentations by the rector of the University of Latvia and by Rusins Freivalds. The rector welcomed the ICALP participants, gave us some interesting information about the University of Latvia and wished us long coffee breaks. Rusins discussed the unity of science, and reminded us that, even at the time of the iron curtain, there was one Computer Science.
The conference proper was kicked off on Monday, 8 July, by an invited talk delivered by the Liverpool-bound Paul Spirakis. Paul's talk was entitled A Guided Tour in Random Intersection Graphs. Random Intersection Graphs are random graphs in which there is a universe M of labels and each one of the vertices selects a random subset of M. Two vertices are connected if, and only if, their corresponding subsets of labels intersect. Random intersection graphs were introduced by M. Karonski, E.R. Sheinerman and K.B. Singer-Cohen and have several applications, as well as a rich theory. Paul's talk provided a survey of the main results on the topic obtained by his research group on combinatorial problems over random intersection graphs, such as independent sets, Hamiltonian cycles, colouring, maximum cliques, expansion and random walks. Paul closed the talk by saying that this model is an excellent area of study for PhD students in TCS.
Tuesday's invited address was delivered by Daniel Marx. Daniel's talk has three chapters (his words) and was entitled The Square Root Phenomenon in Planar Graphs. Its starting point was the observation that most of the classic NP-hard problems remain NP-hard when restricted to planar graphs, and only exponential-time algorithms are known for the exact solution of these planar problems. However, in many cases, the exponential-time algorithms on planar graphs are significantly faster than the algorithms for general graphs: for various problems on planar graphs, one often sees a square root appearing in the exponent of the running time of the best algorithms for their solution. Daniel told his audience that, by now, we have a good understanding of why this square root appears: most of these algorithms rely on the notion of treewidth and its relation to grid minors in planar graphs. Daniel also argued that, under the Exponential Time Hypothesis, one can show that these algorithms are essentially best possible, and therefore the square root must appear in the running time.
In passing, Daniel contributed also one paper to ICALP Track A and one to ICALP Track B!
Susanne Albers delivered the invited talk on Wednesday, 10 July, on Recent Advances for a Classical Scheduling Problem. In her talk, Susanne revisited the classic on-line makespan minimization problem, which has been studied since the 1960s. After presenting the classic results on this problem, starting from Graham's 1966 List algorithm and its competitive analysis, she surveyed recent research on settings in which an online algorithm is given extra information or power while processing a job sequence.
The scientific programme on Thursday, 11 July, started with an invited talk by Orna Kupferman, who gave the only invited address that could be readily classified as belonging to ICALP Track B. Orna's presentation dealt with Formalizing and Reasoning about Quality. Traditionally, formal approaches to the verification of reactive systems are boolean in nature: either a system satisfies its specification or it doesn't. In case a system does not meet its specification, one expects a good verification framework to provide a counter-example, that is, a reason why the system is not correct. Orna and her co-authors have generalized formal specification and verification methods to address the quality of systems. In her talk, Orna introduced the linear temporal logic LTL[F], where F is a set arbitrary functions over the interval [0, 1]. Formulae in LTL[F] are interpreted over computations consisting of sequences of atomic propositions. The satisfaction value of an LTL[F] formula is a number between 0 and 1 that describes how well a computation satisfies a formula. The logic generalizes traditional LTL with the functions in F; examples of functions that might be in F are the maximum or minimum between the satisfaction values of subformulas (these are the quantitative counterparts of boolean OR and AND, respectively), their product and their average. In her talk, Orna showed us how to generalize classic decision problems in formal methods, such as satisfiability, model checking and synthesis, to search and optimization problems in the quantitative setting. This is achieved by means of an extension of the automata-theoretic approach to LTL to the setting of LTL[F].
Before the conference dinner, Jon Kleinberg delivered a special EATCS lecture to celebrate the 40th ICALP. Jon gave an inspiring and very articulate talk entitled Algorithms, Networks, and Social Phenomena. The talk discussed the development of computational models for systems involving social networks and large human audiences. In particular, Jon focused on how information spreads through such systems, and the ways in which this spread is affected by the underlying network structure. Jon said a few times that, despite having so much data at our disposal, we still do not understand human behaviour. However, IMHO, the work by Jon and his coworkers is shedding some light on some aspects of our behaviour.
Peter Widmayer delivered the last invited talk on Friday, 12 July. His presentation was entitled To Be Uncertain Is Uncomfortable, But to Be Certain Is Ridiculous, and was accessible and well paced. The starting point of Peter's talk was a "Socratic dialogue" between a statistical physicist and himself. Traditionally, in combinatorial optimization one assumes that an input instance is given with absolute certainty. The goal is then to find an optimum solution for the given instance. In contrast, as the statistical physicist would argue, input data are in reality uncertain, noisy and inaccurate. As a consequence, an optimum solution to a combinatorial optimization problem might not be meaningful in practice. (For example, the shortest path to our work place we computed yesterday evening might not be usable this morning because of changed traffic conditions.) Peter advocated the development of algorithms that find "meaningful" solutions in the presence of uncertain inputs, proposed an approach towards reaching this goal. and argued that it leads to good solutions in the real world.
Videos of these talks (with the exception of Kleinberg's talk, which, as far as I know, was not recorded) will be available in due course.
Friday, July 12, 2013
ICALP 2013 (Part 1)
ICALP 2013 has just finished. It has been an action packed conference and there has been next to no breathing space. I think that the conference was a great success and the organizers deserve our most heartfelt thanks for all their work.
In case you do not know, the conference has being held in Riga at the University of Latvia. This has been the first time that ICALP has been organized in a country of the former Soviet Union and this was the 40th edition of the ICALP conference. First of all, kudos to the local organizers, who did their very best to make the conference a festive occasion and a very pleasant experience for all the attendees. The city of Riga is very pretty and all ICALP participants had a very warm welcome. The University of Latvia was also enrolling a new batch of students during ICALP and this meant that there was a continuous flow of young and happy-looking people on the university premises. This made the main hall of the university a very lively place to be. We were also blessed with sunny and warm weather, which also helped (especially coming from rainy Iceland).
According to the data presented by Agnis Škuškovniks, on behalf of the organizing committee, to the EATCS council and to the EATCS general assembly, there were 193 registered participants in ICALP 2013, of which 67 are students. Including the local participants, the six invited speakers and the two recipients of the honorary doctorates awarded on Tuesday (Josef Gruska and Juris Hartmanis), 217 people attended ICALP 2013. The pre-conference workshops were attended by 102 participants, which is a very healthy number.
The honorary doctorates were an excellent addition to the standard session devoted to the EATCS Awards. Gruska and Hartmanis delivered lucid and inspirational presentations. It was truly awesome to see Juris Hartmanis deliver an off-the-cuff speech on how he left Latvia and ended up at Cornell as chair of the newly-funded CS department. At 85, he is very articulate and sharp. I had the pleasure of discussing several subjects with him during a very pleasant dinner arranged by the organizers. He is still a truly inspirational figure.
Here are some quick EATCS- and ICALP-related news.
In a subsequent post, which I will write when I get home, I will try to discuss some of the many scientific highlights at ICALP 2013.
To conclude, at the conference I heard that Paul Spirakis is moving to the University of Liverpool. Good luck to Paul!
In case you do not know, the conference has being held in Riga at the University of Latvia. This has been the first time that ICALP has been organized in a country of the former Soviet Union and this was the 40th edition of the ICALP conference. First of all, kudos to the local organizers, who did their very best to make the conference a festive occasion and a very pleasant experience for all the attendees. The city of Riga is very pretty and all ICALP participants had a very warm welcome. The University of Latvia was also enrolling a new batch of students during ICALP and this meant that there was a continuous flow of young and happy-looking people on the university premises. This made the main hall of the university a very lively place to be. We were also blessed with sunny and warm weather, which also helped (especially coming from rainy Iceland).
According to the data presented by Agnis Škuškovniks, on behalf of the organizing committee, to the EATCS council and to the EATCS general assembly, there were 193 registered participants in ICALP 2013, of which 67 are students. Including the local participants, the six invited speakers and the two recipients of the honorary doctorates awarded on Tuesday (Josef Gruska and Juris Hartmanis), 217 people attended ICALP 2013. The pre-conference workshops were attended by 102 participants, which is a very healthy number.
The honorary doctorates were an excellent addition to the standard session devoted to the EATCS Awards. Gruska and Hartmanis delivered lucid and inspirational presentations. It was truly awesome to see Juris Hartmanis deliver an off-the-cuff speech on how he left Latvia and ended up at Cornell as chair of the newly-funded CS department. At 85, he is very articulate and sharp. I had the pleasure of discussing several subjects with him during a very pleasant dinner arranged by the organizers. He is still a truly inspirational figure.
Here are some quick EATCS- and ICALP-related news.
- ICALP 2014 will be held in Copenhagen, Denmark, immediately after SWAT 2013. It will be a four-day ICALP and the general chair for the conference is Thore Husfeldt.
- ICALP 2015 will be held in Kyoto, Japan, and will be co-located with LICS 2015. Kazuo Iwama is the ICALP 2015 general chair. This will be the first ever ICALP outside Europe.
- The EATCS will soon announce and EATCS Fellows programme. The first deadline for nominations will be at the end of this year and we plan to make the first announcement of fellows at ICALP 2014 in Copenhagen.
- The EATCS will begin a new EATCS Young Researcher School Series from 2014. The first school in the series will be organized by Tony Kucera in a beautiful location in Moravia in late July/early August. The theme of the school will be "Automata, Logic and Games".
- Orna Kupferman gave a thought-provoking talk on "The Gender Challenge in TCS" at the EATCS General Assembly. It really got the audience thinking about this important matter.
In a subsequent post, which I will write when I get home, I will try to discuss some of the many scientific highlights at ICALP 2013.
To conclude, at the conference I heard that Paul Spirakis is moving to the University of Liverpool. Good luck to Paul!
Monday, July 08, 2013
Associate and/or assistant professor position in the Language Based Technology section of DTU
I have been asked to advertise this position, which might be of interest to several of my readers and their graduating PhD students/postdocs.
The Language Based Technology section of DTU Applied Mathematics and Computer Science has a new opening for associate and/or assistant professors.
The Language Based Technology section of DTU Applied Mathematics and Computer Science has a new opening for associate and/or assistant professors.
The date for applictions is on October 1st and full details about the call and how to apply are available at
and more information about the Language Based Technology section is available at
We are hoping to attract a brilliant associate or assistant professor to complement our research activities in the
modelling, analysis and realisation of systems using language-based techniques and tools.
Our current expertices include static analysis and model checking
and take place in a number of research centres and research projects
(MT-LAB, IDEA4CPS, TREsPASS, FutureID, SESAMO, PaPP).
We are interested in concurrent, distributed and mobile systems
where reliability and predictability are essential and hence properties
related to safety, security and performance are of key interest; the
systems may include considerations of socio-technical
nature within Systems of Systems.
Friday, June 28, 2013
YouTube channel for the School of Computer Science at Reykjavik University
The School of Computer Science at Reykjavik University has, at long last, created its own YouTube channel. See https://www.youtube.com/user/rucomputerscience.
We are uploading videos of talks from season one of our Pearls of Computation seminar series and from last year's Alan Turing Year events, as well as other
material that might be of general interest.
In case you are interested in following the events we organize, I'd be grateful if you could spend approximately 5 seconds to open the page and click "Subscribe". Thanks in advance!
In case you are interested in following the events we organize, I'd be grateful if you could spend approximately 5 seconds to open the page and click "Subscribe". Thanks in advance!
Wednesday, June 26, 2013
Call for guest bloggers from ICALP 2013
I would like to have some blog coverage for ICALP 2013. If you are attending the 40th ICALP in Riga and you are interested in guest blogging, drop me a line. Ideally, I would like to have a guest blogger for each of the tracks in the conference. You are, of course, also most welcome to blog about the five invited talks and the award ceremonies.
Tuesday, June 25, 2013
PhD Positions at GSSI L'Aquila, Italy - CALL FOR APPLICATIONS
I have been asked to distribute this call for applications for PhD positions in a newly founded international PhD School in Italy, the Gran Sasso Science Institute. I hope that you will encourage some of your best students to apply.
------ PhD Positions at GSSI L'Aquila, Italy - CALL FOR APPLICATIONS -------
Dear Colleagues,
I would like to ask for your help in spreading around the call for application for PhD candidates in Computer Science at the Gran Sasso Science Institute (GSSI)
<http://www.gssi.infn.it/index
We are particularly interested in attracting foreign students. So it would be great if you can deliver this announcement through your emailing lists in your countries.
The deadline for applying to the program is 15th july.
Students will be offered free housing and meals plus the standard three years PhD grant. The official language is English.
GSSI is a new initiative that is starting in L'Aquila as a consequence of the redevelopment plan after the earthquake. The school is managed by INFN (http://www.infn.it/index.php?
There will be other three Phd programs offered by GSSI, one concerning urban studies, one in Physics mainly centered around astro-particles phisics because of the proximity with the famous Lab
(http://www.lngs.infn.it/), and another in Mathematics centered around mathematical modeling.
The school is supported by other three Italian already established graduate schools, IMT in Lucca for computer science (www.imtlucca.it<http://www.im
(http://www.sissa.it/), and Scuola Superiore S. Anna in Pisa for urban studies (www.sssup.it <http://www.sssup.it/> ).
Thank you in advance for your attention and your support.
------ PhD Positions at GSSI L'Aquila, Italy - CALL FOR APPLICATIONS -------
Dear Colleagues,
I would like to ask for your help in spreading around the call for application for PhD candidates in Computer Science at the Gran Sasso Science Institute (GSSI)
<http://www.gssi.infn.it/index
We are particularly interested in attracting foreign students. So it would be great if you can deliver this announcement through your emailing lists in your countries.
The deadline for applying to the program is 15th july.
Students will be offered free housing and meals plus the standard three years PhD grant. The official language is English.
GSSI is a new initiative that is starting in L'Aquila as a consequence of the redevelopment plan after the earthquake. The school is managed by INFN (http://www.infn.it/index.php?
There will be other three Phd programs offered by GSSI, one concerning urban studies, one in Physics mainly centered around astro-particles phisics because of the proximity with the famous Lab
(http://www.lngs.infn.it/), and another in Mathematics centered around mathematical modeling.
The school is supported by other three Italian already established graduate schools, IMT in Lucca for computer science (www.imtlucca.it<http://www.im
(http://www.sissa.it/), and Scuola Superiore S. Anna in Pisa for urban studies (www.sssup.it <http://www.sssup.it/> ).
Thank you in advance for your attention and your support.
Friday, June 07, 2013
Gödel Prize 2013
As some of you might know already, the Gödel Prize 2013, which is awarded jointly by ACM SIGACT and the EATCS, goes to the authors of the following two papers:
The press release issued by the ACM is available at
www.acm.org/press-room/news-
Congrats to the award recipients.
Antoine Joux: A One Round Protocol for Tripartite
Diffie-Hellman, J. Cryptology 17(4): 263-276 (2004). (Conference
version: ANTS 2000)
Dan Boneh, Matthew K. Franklin: Identity-Based Encryption from the Weil Pairing, SIAM J. Comput. 32(3): 586-615 (2003) . (Conference version: CRYPTO 2001)
for their contributions to cryptographic concepts and schemes that provide greater efficiency, flexibility, and security. These papers established the field of pairing-based cryptography by supplying a precise definition of the security of this approach, and providing compelling new applications for it.
Dan Boneh, Matthew K. Franklin: Identity-Based Encryption from the Weil Pairing, SIAM J. Comput. 32(3): 586-615 (2003) . (Conference version: CRYPTO 2001)
for their contributions to cryptographic concepts and schemes that provide greater efficiency, flexibility, and security. These papers established the field of pairing-based cryptography by supplying a precise definition of the security of this approach, and providing compelling new applications for it.
www.acm.org/press-room/news-
Congrats to the award recipients.
Friday, May 10, 2013
Videos as (part of the) solution to assignments
Anna and I are running a three-week, intensive, first-year course in which the students use Uppaal to make models of computing systems and games, and to analyze them using the verification capabilities of that excellent tool. The students find it very easy to use the tool, and can start solving modelling and verification problems with it in a jiffy.
One of the groups of students taking the course delivered a neat video with their solution to one of the problems we posed them. It is the first time I ever received a video as part of a student report. I expect that this will be the first of many.
One of the groups of students taking the course delivered a neat video with their solution to one of the problems we posed them. It is the first time I ever received a video as part of a student report. I expect that this will be the first of many.
Wednesday, April 24, 2013
Call for editor in chief of the Bulletin of the EATCS
The leadership of the EATCS has decided to decouple the production of
the Bulletin of the EATCS (BEATCS) from its editorship. Starting from the October 2013 issue,
the BEATCS will be produced, printed and shipped by our Secretary Office
in Greece. We think that this change was overdue, and that it will help
us improve both the production and the scientific quality of the
BEATCS. From the October 2013 issue, the editor in chief of the BEATCS
will focus solely on the scientific content of the Bulletin.
Our colleague Maria Serna has served as editor in chief of the BEATCS for a long time and has many other commitments. Therefore, we feel that the time has come to appoint a new editor, whose job will be to continue improving the quality and the impact of the Bulletin, in cooperation with the Council of the EATCS and following on Maria's footsteps.
We hereby ask you for expressions of interest to the role of editor in chief of the BEATCS. Each expression of interest for the position should be accompanied by a couple of paragraphs describing your vision for the future of the BEATCS. You are also most welcome to propose suitable candidates for the position other than yourselves.
Please send your nominations to me via email by the 30th of April at the latest.
I take this opportunity to offer Maria Serna our heartfelt thanks, on behalf of the EATCS, for all the work that she has done over the years as editor in chief of the Bulletin. We really appreciate the effort she has put into this important service to the EATCS and the TCS community as a whole.
All the best,
Luca Aceto
President of the EATCS
Our colleague Maria Serna has served as editor in chief of the BEATCS for a long time and has many other commitments. Therefore, we feel that the time has come to appoint a new editor, whose job will be to continue improving the quality and the impact of the Bulletin, in cooperation with the Council of the EATCS and following on Maria's footsteps.
We hereby ask you for expressions of interest to the role of editor in chief of the BEATCS. Each expression of interest for the position should be accompanied by a couple of paragraphs describing your vision for the future of the BEATCS. You are also most welcome to propose suitable candidates for the position other than yourselves.
Please send your nominations to me via email by the 30th of April at the latest.
I take this opportunity to offer Maria Serna our heartfelt thanks, on behalf of the EATCS, for all the work that she has done over the years as editor in chief of the Bulletin. We really appreciate the effort she has put into this important service to the EATCS and the TCS community as a whole.
All the best,
Luca Aceto
President of the EATCS
Two Pearls of Computation Talks at Reykjavík University
Season one of the new Pearls of Computation seminar series at Reykjavik University is in full swing.
On Friday, 15 February 2013, my ICE-TCS colleague Eyjólfur Ingi Ásgeirsson (School of Science and Engineering, Reykjavik University) delivered a talk on E.W. Dijkstra entitled The shortest path to beautiful code ( - DEATH TO GOTO - ).
The following talk was held on Friday, 5 April 2013, when Kristinn R. Thorisson (School of Computer Science, Reykjavik University) delivered a presentation on the work of Marvin Minsky entitled Marvin Minsky: Pioneer, Critic, Optimist.
On Friday, 15 February 2013, my ICE-TCS colleague Eyjólfur Ingi Ásgeirsson (School of Science and Engineering, Reykjavik University) delivered a talk on E.W. Dijkstra entitled The shortest path to beautiful code ( - DEATH TO GOTO - ).
- Recording of the talk (slides and audio) in .avi format.
- Slides with the three "silly games" mentioned in the talk. [Solutions]
- An Interview With Edsger W. Dijkstra by Thomas J. Misa, Communications of the ACM, Vol. 53 No. 8, Pages 41-47.
- E. W. Dijkstra Archive.
- K.R. Apt, Edsger Wybe Dijkstra (1930 -- 2002): A Portrait of a Genius. Formal Aspects of Computing, 14, pp. 92-98, 2002.
The following talk was held on Friday, 5 April 2013, when Kristinn R. Thorisson (School of Computer Science, Reykjavik University) delivered a presentation on the work of Marvin Minsky entitled Marvin Minsky: Pioneer, Critic, Optimist.
- Recording of the talk (slides and audio) in .mp4 format.
- Human Interface video played by Kristinn during the talk.
- NOVA Interview with Marvin Minsky.
Thursday, April 18, 2013
Best paper awards at ICALP 2013
The best paper awards at ICALP 2013 will go to the following papers:
Congratulations to all the recipients of the best paper awards! I look forward to listening to their talks at ICALP 2013.
- Track A: Mark Bun and Justin Thaler. Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities.
- Track B: John Fearnley and Marcin Jurdziński. Reachability in Two-Clock Timed Automata is PSPACE-complete.
- Track C: Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pajak and Przemysław Uznański. Fast Collaborative Graph Exploration.
- Track A: Radu Curticapean. Counting matchings of size k is #W[1]-hard.
- Track B: Nicolas Basset. A maximal entropy stochastic process for a timed automaton.
Congratulations to all the recipients of the best paper awards! I look forward to listening to their talks at ICALP 2013.
Tuesday, April 16, 2013
Accepted papers at ICALP 2013
The list of accepted papers for ICALP 2013 is now available (with and without abstracts). ICALP 2013 is the 40th ICALP conference. I hope to see many of you in Riga to celebrate this event.
Friday, April 05, 2013
Faculty Position in Interactive Storytelling and Game Design at Reykjavik University
The School of Computer Science at Reykjavik University seeks to hire a
faculty member for a new academic position in the field of interactive
narrative and game design. We are interested in an ambitious, highly
qualified academic who can combine innovative teaching and
cutting-edge research in the rapidly evolving area of interactive
digital entertainment within our school.
The faculty position is funded through a collaboration with massively multiplayer game developer CCP Games Inc. We are particularly interested in active researchers who see opportunities in breaking new ground with CCP and with existing faculty within Reykjavík University, in particular within CADIA, the school's artificial intelligence research center. CCP will fund the faculty position for a minimum of 5 years; following that period, CCP and Reykjavík University will seek continued funding for the position. Full academic freedom is respected, however, by both CCP and Reykjavík University.
See here for more information. The application deadline is 30 April 2013 and interviews will be held in May 2013.
The faculty position is funded through a collaboration with massively multiplayer game developer CCP Games Inc. We are particularly interested in active researchers who see opportunities in breaking new ground with CCP and with existing faculty within Reykjavík University, in particular within CADIA, the school's artificial intelligence research center. CCP will fund the faculty position for a minimum of 5 years; following that period, CCP and Reykjavík University will seek continued funding for the position. Full academic freedom is respected, however, by both CCP and Reykjavík University.
See here for more information. The application deadline is 30 April 2013 and interviews will be held in May 2013.
Tuesday, April 02, 2013
LICS 2013 Accepted Papers
This is not news anymore, but the list of accepted papers for LICS 2013 is available here.
As usual, the accepted papers look very interesting and I hope to find the time to read several of them when they become available. (This might be wishful thinking. It seems that finding time to read papers is getting harder by the day, alas.)
For what it is worth, here are two papers that immediately caught my attention browsing through the list of accepted papers and that are available on line.
As usual, the accepted papers look very interesting and I hope to find the time to read several of them when they become available. (This might be wishful thinking. It seems that finding time to read papers is getting harder by the day, alas.)
For what it is worth, here are two papers that immediately caught my attention browsing through the list of accepted papers and that are available on line.
- Dexter Kozen, Kim Guldstrand Larsen, Radu Mardare and Prakash Panangaden. Stone Duality for Markov Processes.
- Mikołaj Bojańczyk, Bartek Klin, Sławomir Lasota and Szymon Toruńczyk. Turing Machines with Atoms.
Theorem: In sets with equality atoms, there is a language that is decidable in nondeterministic polynomial time, but not deterministically semi-decidable.Before you get carried away, here is what the authors write below the statement of this theorem.
A consequence of the theorem is that, with atoms, P is not equal to NP. It is not our intention to play up the significance of this result. In a sense, the theorem is too strong for its own good: it shows that computation with atoms is so different from computation without atoms, that results on the power of nondeterminism in the presence of atoms are unlikely to shed new light on the power of nondeterminism without atoms.Congratulations to all the authors of accepted papers.
Sunday, March 31, 2013
BCS Lovelace Medal to Samson Abramsky
Happy Easter news for the TCS community. Samson Abramsky is being awarded the British Computer Society (BCS) Lovelace Medal for 2013. (The press release is here.) The BCS Lovelace Medal was established in 1998 in honour of Lady Augusta
Ada Byron, Countess of Lovelace and daughter of Lord Byron. The Medal is
presented annually to individuals who, in the opinion of BCS, have made
a significant contribution to the advancement of Information Systems.
Quoting Samson,
Congratulations to Samson!
Quoting Samson,
It is particularly pleasing that this award recognizes work of a highly foundational character, and shows the commitment of BCS to support the study of computing not only for its manifold applications, but as a fundamental scientific discipline in its own right.As the press release states, Samson
is pre-eminent in setting the modern agenda in the foundations of computer science, an area where he has made immense contributions since the 1980s. His contributions in each of the past three decades had a major impact on the field, notably: Domain Theory in Logical Form, Game Semantics and Categorical Quantum Mechanics. He has shown the ability to change research fields and to establish new interdisciplinary approaches. His work over the past decade has shown that methods and concepts developed in theoretical computer science can be applied very directly in quantum information, and the foundations of quantum mechanics itself.Another recent example of application of methods from "volume B TCS" to other fields is in this short paper, where Samson and Wiktor Winschel apply coalgebraic and other structural methods originating from computer science to economics and game theory.
Congratulations to Samson!
Saturday, March 23, 2013
Thursday, March 21, 2013
How to write an unsuccessful letter of nomination for an award
The following piece of text has been going through my head since the meeting of an award committee I attended earlier this week. I had to get rid of it by writing it
down. So here it is, for your reading pleasure. I thought that it was
best to choose a "How to have your abstract rejected" style for this
piece.
You have just seen the call for nominations for an award and you have an excellent candidate for this accolade in mind. The call for nominations asks for a letter of nomination and gives some criteria that a nominee for the award should satisfy. How can you increase the chances that your nomination will be unsuccessful? The aim of this short piece is to present some simple approaches that are guaranteed to increase the chances that your nomination will be unsuccessful, even if you were nominating Albert Einstein for the Relativity Award 2013.
The first step in ensuring lack of success of a nomination is not to read the guidelines in the call for nominations. This will make it highly likely that your letter will not address at least some of the criteria that a good nomination should have. However, this leaves open the possibility that, by chance, your letter of nomination address some of the most important criteria for nominating your candidate. The best approach to prevent this from happening is to be systematic. Do read the call for nominations and make sure that you avoid addressing each of the criteria listed there. For example, if the call asks for (a link to) a CV, do not provide any!
However, the systematic approach requires precious time, effort and organization. Isn't there a better way to achieve your goal of submitting an unsuccessful nomination without sweating too much? Indeed there is! The perfect, no-sweat unsuccessful letter of nomination is a one liner that reads:
You have just seen the call for nominations for an award and you have an excellent candidate for this accolade in mind. The call for nominations asks for a letter of nomination and gives some criteria that a nominee for the award should satisfy. How can you increase the chances that your nomination will be unsuccessful? The aim of this short piece is to present some simple approaches that are guaranteed to increase the chances that your nomination will be unsuccessful, even if you were nominating Albert Einstein for the Relativity Award 2013.
The first step in ensuring lack of success of a nomination is not to read the guidelines in the call for nominations. This will make it highly likely that your letter will not address at least some of the criteria that a good nomination should have. However, this leaves open the possibility that, by chance, your letter of nomination address some of the most important criteria for nominating your candidate. The best approach to prevent this from happening is to be systematic. Do read the call for nominations and make sure that you avoid addressing each of the criteria listed there. For example, if the call asks for (a link to) a CV, do not provide any!
However, the systematic approach requires precious time, effort and organization. Isn't there a better way to achieve your goal of submitting an unsuccessful nomination without sweating too much? Indeed there is! The perfect, no-sweat unsuccessful letter of nomination is a one liner that reads:
I nominate X for award Y. Best regards, Z
Submitting
this letter template, which you should feel free to reuse, will
strongly indicate to the award committee that is in charge of evaluating
the nominations and of selecting the award recipient(s) - that you really do not know why the nominee deserves the award, and
- that you are not
willing to invest any time and effort in finding out why the nominee is
worthy of the honour and in convincing the committee that (s)he is the
one to select.
Subscribe to:
Posts (Atom)