CadiaPlayer GGP Champion Again!

I am proud to announce that the general-game-playing agent CadiaPlayer, developed at my own department by Yngvi Björnsson, Hilmar Finnsson, Stefán Freyr Guðmundsson and Stephan Schiffel, won this year's General Game Playing competition hosted at the AAAI conference, thereby reclaiming the title it lost in 2009.  On its road to the title it defeated among others the winners from the previous two years. As a winner of the competition CadiaPlayer also played an exhibition match consisting of three games against a human player --- Chris Welty from IBM --- and won convincingly.

With this title CadiaPlayer has become the most victorious GGP agent ever, and the only agent so far to win the competition three times.

Congratulation to the CadiaPlayer team!

PhD positions at IMT Lucca (reprise)

I am happy to post a revised version of the call for PhD positions at IMT Lucca that I received today from Alberto Lluch Lafuente and Rocco De Nicola. Distribute the announcement as you see fit.

 
The Institute for Advanced Studies IMT Lucca - Italy (http://www.imtlucca.it/) announces 36 PhD scholarships providing about €13,600 EUR gross yearly plus accommodation and full board. Deadline for application is September 26, 2012.

IMT Lucca (Italy) is an Institute for Advanced Studies and an International Graduate School that acts as a research university with the aim of forming human capital in disciplines characterized by their high potential for concrete application. IMT strives to reach the fusion of theoretical comprehension and practical relevance.

PhD programs are taught exclusively in English. The PhD Program includes a Track in Computer, Decision and Systems Science with a specific Curriculum in Computer Science. The track is coordinated by Rocco De Nicola and aims at preparing researchers and professionals with a wide knowledge of the theoretical foundations of computer science and informatics, control systems and optimization, image analysis, and management science.

The curriculum in Computer Science focuses on languages, models, algorithms, and verification methods for modern distributed systems. PhD students following the curriculum in Computer Science will perform their activities in collaboration with the SysMA research unit (http://sysma.lab.imtlucca.it/) on system modelling and analysis. This research unit focuses on formal languages, models, methodologies and tools to support the development of correct software systems with high quality in terms of predictability, security, efficiency, usability, re-usability, maintainability, and modularity.

We hope that you might consider applying

http://www.imtlucca.it/phd/call_for_applications/

If you are not personally interested, please help us signaling these opportunities to colleagues and collaborators. For further information please contact Alberto Lluch Lafuente or Rocco De Nicola.

Samson Abramsky discusses the legacy of Turing

Readers of this blog might be interested in this podcast by the Royal Society in which Samson Abramsky discusses the legacy of Turing. Samson is one of the editors of The foundations of computation, physics and mentality: the Turing legacy, a special issue of Philosophical Transactions of the Royal Society A devoted to "the richness of Alan Turing’s intellectual legacy in the modern conception of computation."

Enjoy!

Random thoughts on conference presentations

1. When giving an invited talk at a general TCS conference, do not assume that everyone in the audience is interested in the technicalities of your subject. Focus on the main message, tell the story of the ideas and why you think they are important. Give everyone something to take home. 
2. Do not assume that you do not need to introduce the setting for your work because someone else has done it before or on an earlier conference day. Not everyone will have attended the talks where the background and motivation were presented.
3. Do not run over time.
4. Never speak with your hands on your mouth, even if it feels good :-)
5. Do not let your voice drop to an inaudible level as your sentence progresses. Dare to speak slowly and loudly.
6. Ask yourself: How many slides do I really need for a 20-minute talk? Most of us will only use a few, and those should convey the message of the talk at a suitable level of abstraction.
   

The advice we give others is the advice we ourselves need.

ICALP 2012: Days 3-5

At long last, here are some of my notes from the main events that took place during the last three days of ICALP 2012. There were several excellent talks at Track B (which is the one I attended) and I hope to find the time to discuss some of my favourite papers at some point.

Day 3 was given the best of starts by Gilles Dowek's invited talk entitled A theory independent Curry-de Bruijn-Howard isomorphism. (The slides are here and the abstract is here.) IMHO, Gilles pitched his talk at precisely the right level for a general conference in TCS like ICALP and my impression was that he gave each attendee something to take home, regardless of their area of expertise.

Gilles introduced the seminal Curry-de Bruijn-Howard isomorphism, which was in fact originally proposed by Brouwer, Heyting, and Kolmogorov, who suggested to de fine constructive proofs as algorithms. He surveyed the principles behind the plethora of existing proof processing systems and the principles that led to the development of the universal proof checker Dedukti. Oversimpliying, Dedukti is based on what Gilles called Hilbert and Ackermann’s paradise: one logic and many theories. The logic is the lambda-Pi-calculus proposed by Harper, Honsell and Plotkin. However, theories are represented using rewrite systems, rather than using axioms. Indeed, according to Gilles, "Axioms suck!" (from the point of view of efficiency).

Overall, I enjoyed the talk by Gilles a lot. It was a pity that it was not as well attended as it should have been.

At the start of day 4, Dan Spielman gave an excellent talk on using graph theory to solve linear equations. The talk was entitled Algorithms, Graph Theory, and the Solution of Laplacian Linear Equation and the Laplacian was the main character in the story that Dan recounted with verve and clarity. For further reading on this topic, Dan himself suggested this article by Erica Klarreich at the Simon's Foundation. In passing, Dan also described a method for obtaining "obscenely accurate solutions to a problem by solving a simpler one". 


I had had the pleasure to hear Dan deliver a talk on smoothed analysis when he was a co-recipient of the Gödel Prize 2008 in Reykjavík and I watched the video of his talk at the latest ICM. IMHO, the invited talk at ICALP 2012 confirmed him yet again as one of the very best speakers around. 


Day 4 at ICALP 2012 was also devoted to the awards of the Gödel Prize 2012 and of the EATCS Award. As you surely know already, the Gödel Prize went to three seminal papers in the field of Algorithmic Game Theory. Christos Papadimitriou delivered a talk on behalf of the recipients of the Gödel Prize, who were all . present at the conference apart from Noam Nisam. Christos explained the intellectual roots of the concept now known as the price of anarchy and of algorithmic mechanism design. Moreover, he asked the question: What makes an idea spread? His answer was that an idea spreads if it gives young researchers an opportunity to show how smart they are! 


Christos concluded his talk by being a prophet of doom. (I am using his own words here.) He reminded the people in the audience that, for people like me, the "Hello World" program was Max, a program for finding the largest entry in an array of integers, say. The world has changed. Computation has changed. The inputs to our programs are selfish agents who are interested in the outcome of our computation. Vickrey is the new Max :-)

The EATCS Award went to Moshe Vardi (laudatio), who delivered a presentation entitled  A Logical Revolution. In the talk, Moshe described how logic has one from irrelevance to relevance in our field. The key lessons in this rise of logic are the importance of algorithms, heuristics and tools. One of the key insights is that one should not be scared of worst-case complexity: It always barks, but it does not always bite! Efficient in the field of logic in computer science means exponential. "Exponential is the new polynomial." 

Both award presentations were excellent and were given a long round of applause from a packed audience. 


The last invited talk at ICALP 2012 was delivered by Kohei Honda. Kohei´s talk was entitled Session types and distributed computing. It described the origins of the notion of session type and how sessions types find application in the NSF Ocean Observation Initiative. This represents one of the most impressive applications of notions from concurrency theory outside computer science. Kohei is also one of the prime movers behind the programming language Scribble. His talk was a fitting finale to an excellent ICALP conference.

Thanks again to Artur Czumaj and his team for arranging an excellent conference in the beautiful setting of the University of Warwick.

ICALP 2012: First two days

ICALP 2012 is taking place at the University of Warwick. The programme is action packed, with many highlights and prizes. There are three tracks with 123 selected papers (71 for track A, 30 for track B and 22 for track C) out of 432 submissions (248 for track A, 105 for track B and 79 for track C). The acceptance rate was therefore around 28.5%. In addition, there are five invited talks and on day two David Harel delivered a Turing talk.

The conference is being attended by 210 participants (146 regular and 64 students).

There is so much going on that it is hard to give a detailed report on the scientific activities. I will thus limit myself to a few short remarks on some of the highlights of the first two days of the conference.

• The first two invited talks were delivered by Stefano Leonardi (Sapienza University of Rome) and Berthold Vöcking (RWTH Aachen). Both speakers focussed on algorithmic aspects of auctions. Stefano's talk was entitled On Multiple Keyword Sponsored Search Auctions with Budgets, while the talk by Berthold dealt with Randomised Mechanisms for Multi-Unit Auctions. 
• Leslie Ann Goldberg delivered a very inspiring talk on her joint paper with Mark Jerrum The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation), which received the best paper award for track A. Leslie brilliantly conveyed her enthusiasm for this amazing polynomial even to a layman like me, and gave us a glimpse of the rich mine of information that the Tutte polynomial contains about a graph. (W. T. Tutte also figured prominently during the very instructive excursion to Bletchley Park we enjoyed yesterday.)
• Manfred Kufleitner presented his joint work with Volker Diekert, Klaus Reinhardt and Tobias Walter that received the best paper award for Track B. Their truly remarkable result settles a long-standing open problem in formal language theory and may be found in the paper Regular Languages are Church-Rosser Congruential.  
• Tuesday saw an excellent Turing talk by David Harel on three strands of his research over the years that have been influenced by Turing's work.  I enjoyed it a lot and I finally got a chance of hearing David Harel deliver one of his trademark talks. 
• The Presburger award went to Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs). Venkat gave a talk that highlighted the web of connections that arise in his work and how tools from one area can find application in another one. He ended his talk was quoting the title of a talk by Avi Widgerson, namely "Depth through breadth". Mikkel Thorup gave a heartfelt presentation, describing Mihai Patrascu's work and personality. Several participants took photos for the Cheers to Mihai! web site. 
• The EATCS general assembly lasted until 8.50pm. Kurt Mehlhorn gave a very entertaining and thought-provoking report from the PC chairs. He said, amongst other things, that the submission data show that Track A researchers like to work in pairs or triples, Track B people like to work in pairs and that Track C papers are typically co-authored by a group of people. 
• ICALP 2014 will be held at the IT University in Copenhagen with Thore Husfeldt as general chairs. SWAT 2014 will take place just before ICALP and you will be able to enjoy the Copenhagen Jazz Festival too!

The conference is being organized by Artur Czumaj and his team. Kudos to them for having done a truly excellent job. Thanks to all of them!

I will try to post a telegraphic report on the rest of the conference as soon as I have a little time. I hope that other ICALP participants will share their opinions on the conference and their short reports as comments to my quarter-baked posts. 

LICS Test-of-Time Awards 2012

Prakash Panangaden has informed me that the LICS Test-of-Time Award for 2012 has gone to the following two papers:

• Thomas A. Henzinger, Xavier Nicollin, Joseph Sifakis and Sergio Yovine. Symbolic Model Checking for Real-Time Systems. 
• Jean-Pierre Talpin and  Pierre Jouvelot. The type and effect discipline.

The first article has received a huge number of citations for a LICS paper (1172 according to Google Scholar). It develops a thorough theory of symbolic model checking for timed CTL over finite automata with real-valued clocks.  It presents an algorithm that computes the set of states that satisfy a formula symbolically as a fixed point of a functional on state predicates, without constructing the state space. For this purpose, the authors introduce T_mu, a mu-calculus on computation trees over real-numbered time that has been studied by other researchers in further developments, and investigate its expressive power relative to that of timed CTL. Overall, this has been an influential contribution for the fragment of the CAV community dealing with real-time systems.

The second paper has been recognized an an important contribution to the theory of types and has received 331 citations  according to Google Scholar. The type and effect discipline is a framework for reconstructing the principal type and the minimal effect of expressions in implicitly-typed polymorphic functional languages that support imperative constructs.

Congratulations to the award recipients!

PhD Positions at IMT Lucca

IMT Lucca has issued its call for applications for admission to the IMT Ph.D. Program beginning in January 2013. Readers of this blog (or their students) might be interested in the track called Computer, Decision, and Systems Science, whose director is Rocco De Nicola.

The raw data about this call for PhD applications are as follows:

• 36 Ph.D. positions are covered by scholarships in the gross amount of 13,638.47€ /year.
• A limited number of additional positions without scholarships may also be offered.
• Ph.D. students will have tuition fees waived.
• Ph.D. students who are granted a scholarship have free accommodation in shared double rooms in the School residence halls (with the exception of students whose permanent residence is within 30km of IMT).
• Ph.D. students will have free access to the canteen services.
• Ph.D. students are covered by insurance against any accident and/or injury that may occur while they carrying out their Ph.D. activities.

For more information about IMT, I encourage you to look at their excellent recruitment video. IMT is growing and promises to become a hotbed of research at the intersection of computer science, control theory, economics and statistical physics. At least, the level of ambition is high.

Let me add, as icing on the cake, that Lucca is a lovely little town, which is close to many other beautiful Italian cities. Encourage good students to apply for the advertised positions!

Best paper awards at ICALP 2012

The preliminary version of the detailed programme for ICALP 2012 is now available here. While skimming through the programme, I learnt that the best paper awards for the conference will go to the following papers:

• Leslie Ann Goldberg and Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation). Best paper for Track A. 
• Volker Diekert, Manfred Kufleitner, Klaus Reinhardt and Tobias Walter. Regular Languages are Church-Rosser Congruential. Best paper for Track B.
• Piotr Krysta and Berthold Vöckin. Online Mechanism Design (Randomized Rounding on the Fly). Best paper for Track C.

The best student papers are:

• Anastasios Zouzias. A Matrix Hyperbolic Cosine Algorithm and Application. Co-recipient of the best student paper for Track A.   
• Shelby Kimmel. Quantum Adversary (Upper) Bound. Co-recipient of the best student paper for Track A. 
• Yaron Velner. The Complexity of Mean-Payoff Automaton Expression. Best student paper for Track B.
• Leonid Barenboim. On the Locality of NP-Complete Problems. Best student paper for Track C.

Congratulations to all the award recipients!

The scientific programme for ICALP 2012 looks really action packed. The invited speakers are:

• Gilles Dowek (INRIA Paris)
• Kohei Honda (Queen Mary London)
• Stefano Leonardi (Sapienza University of Rome)
• Daniel A. Spielman (Yale)
• Berthold Vöcking (RWTH Aachen)
• Alan Turing talk: David Harel (The Weizmann Institute of Science)

During the conference, there will be presented three special awards: EATCS/ACM SIGACT Gödel Prize 2012, EATCS Award 2012, and EATCS Presburger Award 2012.

• EATCS and ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) awarded the Gödel Prize 2012 to three groups of researchers for their contributions to understanding how selfish behavior by users and service providers impacts the behavior of the Internet and other complex computational systems. The papers were presented by Elias Koutsoupias and Christos H. Papadimitriou, Tim Roughgarden and Éva Tardos, and Noam Nisan and Amir Ronen.
• The Presburger Award Committee 2012, consisting of Monika Henzinger, Antonin Kucera, and Stefano Leonardi (chair), has unanimously decided to propose Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs) as joint recipients of the 2012 EATCS Presburger Award for young scientists. (pdf)
• The EATCS Awards Committee consisting of Leslie Ann Goldberg, Friedhelm Meyer auf der Heide and Eugenio Moggi (chair), has unanimously decided to give the 2012 EATCS Award to Moshe Vardi (Rice University). (pdf)

The main conference will be preceded by a series of workshops taking place on Sunday, July 8.

Accepted papers at ICALP 2012

The list of papers that have been selected for the three tracks of ICALP 2012 is now available. The preliminary programme is also on line. This looks like an action-packed ICALP, with a plethora of interesting invited talks, award sessions and good-looking papers. I look forward to the conference.

EATCS and Presburger Awards for 2012

It is award time for the EATCS.

The EATCS Award for 2012 will go to Moshe Vardi. (The award is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career.) You can read the laudatio here.

The Presburger Award Committee 2012 has unanimously decided to propose Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs, New York) as joint recipients of the 2012 EATCS Presburger Award for young scientists. See here for the details.

Congratulations to all the recipients of the two awards! 

Fifth Talk in the Alan Turing Year at Reykjavík University

The fifth talk in the Alan Turing Year at Reykjavík University was delivered this afternoon by my colleagues Yngvi Björnsson and Kristinn R. Thórisson. The talk was entitled Alan Turing's Contributions to Artificial Intelligence: Can Machines Think? and has been organized in collaboration with CADIA and IIIM. This was a thought-provoking and very enjoyable scientific event. In case you are interested the audio and the slides of the talk are here in .avi format. (Note: For technical reasons only the audio of Kristinn's presentation is available.)

In his presentation, Yngvi introduced the field of AI, its subbranches (applied AI, strong AI and cognitive AI) and highlighted Turing's main contributions to the field. On the other hand, Kristinn presented a critique of the Turing Test. Kristinn is a firm supporter of strong AI and his position on this matter can be summarized as follows. (I hope that I am not misrepresenting his views too much.)

1. The standard divide-and-conquer approach that we use in science to understand phenomena is not going to help us understand "intelligence", at least not if applied in the same way as has been done so far in AI, namely by using it in a reductionist way to remove features that are central to the phenomenon of intelligence.
2. The Turing Test was a very premature attempt at devising a test for the phenomenon of intelligence that forced upon much constructionist AI research the view that "intelligence is X, where X is some very simple manifestation of natural intelligence."

Overall, I left the talk with plenty to muse on, assuming I will have the time and the brains for this activity.

Reading material:

• “Computing machinery and intelligence” by Alan Turing (1950) (hosted by Hugh Loebner)
• The Turing test entry in the Stanford Encyclopedia of Philosophy.

PC-chair-authored papers at conferences

Perhaps it is just me, but I feel that there has been an increase in the number of papers (co-)authored by PC chairs selected for presentations at conferences. This seems to happen mostly at "specialist" conferences. I have noticed a similar trend for special issues of journals, to which guest editors are often allowed to submit contributions. In that case, the submission is handled by a member of the editorial board as an ordinary paper submitted to the journal.

Is it just me? If not, do you think that this is a good development?

Assistant professor position at Chalmers University of Technology

I have been asked to spread the news about this position. It looks like a very exciting opportunity for an ambitious young scientist.

We're looking for a talented and ambitions Assistant Professor in Information and Communication Technology at Chalmers University of Technology, Gothenburg, Sweden.

The position includes at least 80% research time and prestigious
status of Area of Advance at Chalmers:
http://www.chalmers.se/en/areas-of-advance/ict/Pages/default.aspx

The area of security is well in scope of the position. Please, help
spread the word!

Application deadline: May 1, 2012

Further info and application link:
http://web1.reachmee.com/i003/chalmers/se/vacdetail.aspx?commadseqno=502&postback%20=%20vacancies.aspx

J.E. Littlewood's take on "research strategy"

I really enjoyed reading the post Are You Working too Hard?, watched the linked videos and read some of the accompanying material from Uri Alon's web site. Whenever I stumble across this kind of material, I tend to go back to one of my favourite sources of inspiration related to the academic's art of work, namely the delightful piece The Mathematician's Art of Work by J.E. Littlewood. In that piece, "with a good deal of diffidence", Littlewood tries to give "some practical advice about research and the strategy it calls for."  Here is a summary of his advice.

• On days free for research, Littlewood recommends working at most five hours with breaks about every hour (for walks perhaps). Littlewood claims that without breaks one acquires the habit of slowing down unconsciously.
• Either work all out or rest completely. It is too easy to fritter a whole day away with the intention of working but never getting properly down to it.
• For a week without teaching duties, take one afternoon and the following day off. The day off should stay the same each week. 
• Take three weeks of holiday at the beginning of each vacation. This period is necessary and sufficient for recovering from the severest mental fatigue. 
• Morning work is far better than work done at other times of the day. From a certain point onwards, following severe concussion in 1918, Littlewood never worked after 6.30pm.
• Try to end your day's work in the middle of something; in a job of writing out, stop in the middle of a sentence. This will help warming up the morning after. 
• An ominous symptom of overwork is an obsession with the importance of work, and filling every moment to that end.

How would your work pattern compare to these pieces of advice? In my case, the answer would not be pretty and I feel that the same applies to many of my closest colleagues. The obsession with the importance of work has been there for a while and ........

Accepted papers for LICS 2012

The list of accepted papers for LICS 2012 is now out.

The first thing to note is that the PC for LICS 2012 has selected 61 submissions for presentation at the conference. By way of comparison, there were 37 papers that were presented at LICS 2011 (modulo counting mistakes I might have made.) This increase in the number of selected papers follows one of the changes that LICS 2012 promised to implement:

In response to concerns about LICS becoming overly selective with a too-narrow technical focus, the program committee will employ a merit-based selection with no a priori limit on the number of accepted papers.

Does this higher number of selected papers imply a "decrease in the quality of the conference programme", whatever that may mean? I have not read the papers yet, but a quick look at the list of selected papers and a brief look at the introduction of some of those available on line seem to indicate that this installment of LICS will be at least as strong as the others. Time will tell. My gut feeling is that this will be a very exciting conference.

I hope that someone attending the conference will be willing to send me a report for this blog. Let me know if you are interested in sending me a short report from LICS 2012.

Holding LICS in Croatia will be an interesting experiment. LICS 2012 will be hosted by the University of Dubrovnik, in Dubrovnik, which is a lovely town along the Adriatic sea. The location and the quality of the conference programme should entice many colleagues to attend the event. Unfortunately, the early registration fee looks pretty hefty to me: $450 for ACM, IEEE or ASL members and $600 for non-members are a lot of money at a time when travel money is scarce. (By way of comparison, the registration fee for ICALP 2011 in expensive Zurich was roughly €334.)

Last, but not least, it will be interesting to see which papers will receive the LICS Test-of-Time Award for 2012. Do you have any predications you'd like to share in the comment section?

Endre Szemerédi has been awarded the Abel Prize for 2012

Timothy Gowers just announced that  Endre Szemerédi has been awarded the Abel Prize for 2012. The citation reads:

"for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions on additive number theory and ergodic theory."

This is a truly major day for discrete mathematics and TCS.  Look at  the Abel Prize web site and at the written version of the talk by Timothy Gowers,  addressed to a general audience, for more details.

ICE-TCS Annual Report for 2011

The ICE-TCS annual report for 2011 is now available. The main aims of our small centre are to establish TCS as a visible research area in Iceland, to attract students to it and to organize high quality TCS events in the country. We have been at it since 2005 and we hope to keep going.

Third Talk in the Alan Turing Year at Reykjavík University

The third talk in the Alan Turing Year at Reykjavík University was delivered last Thursday by Bjarni V. Halldórsson and dealt with Alan Turing's work on mathematicalbiology. (The event was organized jointly with the Icelandic Mathematical Society.) The audio of the talk is here in .avi format. The slides for the talk are here in .pdf format. Enjoy. 

This coming Thursday, Magnús M. Halldórsson will deliver a talk entitled The million dollar question: P vs. NP, and the legacy of Turing. I will post the audio of the talk as soon as it becomes available.

What does our job as academics consist of?

At this time of the year, my university produces its annual magazine. For good or for worse, typically I cannot resist the temptation to put pen to paper and to contribute one or two pieces to that publication. This year has been no exception, and I ended up writing a piece, aimed at students and the general public, that tries to explain what our jobs consist of. The reason for offering this specific contribution to the university magazine is that I have been feeling for a while that our students do not know what we do. And if they do not, what are the chances that anyone else will?

The result is Unveiling the Ivory Tower: The academic's art of work, just in case it may be of interest to any of my readers.