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!
Thursday, July 26, 2012
Tuesday, July 24, 2012
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/
We hope that you might consider applying
http://www.imtlucca.it/phd/
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.
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/
We hope that you might consider applying
http://www.imtlucca.it/phd/
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.
Friday, July 20, 2012
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!
Wednesday, July 18, 2012
Random thoughts on conference presentations
- 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.
- 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.
- Do not run over time.
- Never speak with your hands on your mouth, even if it feels good :-)
- Do not let your voice drop to an inaudible level as your sentence progresses. Dare to speak slowly and loudly.
- 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.
Monday, July 16, 2012
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.
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.
Thursday, July 12, 2012
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.
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.
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!
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.
Subscribe to:
Posts (Atom)