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

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

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

Enjoy!

Best paper awards at ICALP 2013

The best paper awards at ICALP 2013 will go to the following papers:

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

The best student paper awards will instead go to:

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

None of the accepted papers for Track C was a student paper.

Congratulations to all the recipients of the best paper awards! I look forward to listening to their talks at ICALP 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.

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.

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.

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

To whet your appetite, here is what is probably the main result in the latter paper.

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.