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!

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.

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.php/en/announcements-all/400-ph-d-call-forapplications>

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?lang=en) and will start a PhD program in Computer science that is centered around new generation computing, including distributed, ubiquitous and autonomous systems, with emphasis on three main disciplinary pillars: algorithms, software engineering and specification and analysis.

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.imtlucca.it/> ), SISSA in Trieste for mathematics and physics
(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.

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:

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.

 

The press release issued by the ACM is available at

www.acm.org/press-room/news-releases/2013/goedel-prize-13/

Congrats to the award recipients.

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.

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.

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,

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!

Does it also work in theory?

Courtesy of Robbert Dijkgraaf's media page.

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:

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)

1. that you really do not know why the nominee deserves the award, and
2. 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.
   

Is there a better way of achieving your goal? If so, I should really like to know.

Monotasking vs. multitasking

I am enjoying reading Out of Their Minds (The Lives and Discoveries of 15 Great Computer Scientists) by Dennis Shasha and Cathy Lazere. IMHO, the book does a great job in making the lives and ideas of some of the leaders in our field accessible to a general public. I will recommend it to my students and to the colleagues of mine who will prepare future Pearls of Computation seminars.

At the end of the chapter devoted to Donald E. Knuth,  the authors quote Don Knuth as saying:

I do one thing at a time. This is what computer scientists call batch processing---the alternative is swapping in and out. I do not swap in and out.

This quote reminded me a TED talk, in which Italian designer Paolo Cardini encourages his audience to consider the virtues of monotasking.

For several years in my career, I was largely a monotasking person. In my research, I mostly worked on one thing at the time. However, this has changed substantially over the years.  Now I find myself multitasking and context switching a lot and this leads to more stress at work. I guess that most of us have a similar story to tell; the length of the list of things to do increases much faster than our ability to get things done, alas.

Stephen Cook receives the Gerhard Herzberg Canada Gold Medal for Science and Engineering

Stephen Cook has received Canada's highest honour,  the Gerhard Herzberg Canada Gold Medal for Science and Engineering. More on Stephen Cook's Herzberg Canada Gold Medal can be found here.

EATCS Award 2013 to Martin Dyer

The EATCS Awards Committee, consisting of Leslie Ann Goldberg, Vladimiro Sassone and Friedhelm Meyer auf der Heide (chair), has unanimously decided to give the EATCS Award to Martin Dyer. The laudatio for Martin Dyer is available here. Martin's Wikipedia page mentions his key achievements in

(1) - polynomial time algorithm for approximating the volume of convex bodies (with Alan Frieze and Ravindran Kannan)
(2) - linear programming in fixed dimensions
(3) - the path coupling method for proving mixing of Markov chains (with Russ Bubley)
(4) - complexity of counting constraint satisfaction problems.

In addition, the laudatio singles out his work with Alan Frieze on developing the probabilistic analysis of algorithms. Dyer and Frieze showed that many NP-hard problems arising in combinatorial optimisation can be solved in polynomial expected time when the instances are drawn from natural distributions.

Congratulations to Martin!

Friday Fun

 

Source: One of the Computer Science students at Reykjavík University

Erik Demaine receives the EATCS Presburger Award 2013

The Presburger Award Committee, consisting of Peter Widmayer, Antonin Kucera and Monika Henzinger (chair), has unanimously decided to propose Erik Demaine (MIT, USA) as recipient of the 2013 EATCS Presburger Award for young scientists. Congratulations to Erik!

The Presburger Award is sponsored by CWI, Centrum Wiskunde & Informatica.

The citation for the award reads as follows.

Erik Demaine, born in 1981, has made outstanding contributions in several fields of algorithms, namely computational geometry, data structures, graph algorithms and recreational algorithms. In computational geometry and data structures he has solved or made significant progress on classic problems such as the carpenter’s rule problem, the hinged-dissection problem, the prefix-sum problem, and the dynamic optimality conjecture. In graph algorithms he used the powerful theory of graph minors to develop a suite of algorithms for approximately solving a general family of intractable problems. He also started the new field of computational origami, where his book is the leading authority in the field. His work  has shown promising applications to computer graphics, sensor networks, molecular biology, programmable matter, and manufacturing and engineering.

The committee recommends Erik Demaine as an exceptional young scientist who fully deserves the Presburger Award.

The committee would also like to mention that the quality of all nominations submitted this year was very high. The Presburger Award is attracting the best young scientists in the field of theoretical computer science worldwide.

Addendum, 14 February 2013: Check out a Popular Science article on Erik's work here:  http://www.popsci.com/science/article/2013-01/dazzling-sometimes-absurd-always-playful-genius-erik-demaine.

Poster for the Pearls of Computation seminar series

The poster has been designed by the talented team at Podpunkt. In case you need a good design for book covers, logos or posters, you might wish to consider them. Look at their portfolio and enjoy their work. As I remarked in an earlier post, the Podpunkt studio has strong connections with mathematics and TCS.