The logo of ICE-TCS is courtesy of Emilka Bojanczyk.

ICE-TCS Theory Day 2012

Programme

17 August 2012, Reykjavik, Iceland

Room M1.03, Reykjavik University, Menntavegur 1


The ICE-TCS Theory Day for 2012 will consist of two sessions. The first session will be dedicated to technical presentations accessible to a general computer science and mathematics audience. The second session will celebrate the award of the Gödel Prize 2012 to three papers in algorithmic game theory and mechanism design and of the EATCS Award 2012 to Moshe Vardi, who is a member of the scientific advisory board of ICE-TCS.

Session devoted to contributed talks
14:00-14:20 Yngvi Björnsson
The science behind CadiaPlayer
14:20-14:40 Hjalti Magnússon
Turning the study of stack-sortable permutations into algorithmics
14:40-15:00 Helga Guðmundsdóttir
Putting Theory to the Test: Distributed Connectivity in Wireless Networks
15:00-15:15 Coffee break
Award session
15:15-15:30 Magnús M. Halldórsson
The 2012 Gödel Award
15:30-15:45 Luca Aceto
The Work of Moshe Vardi, Recipient of the EATCS Award 2012

Abstracts

The abstracts are listed in order of presentation.


Yngvi Björnsson. The science behind CadiaPlayer.
Abstract: The aim of General Game Playing (GGP) is to create intelligent agents that can automatically learn how to play many different games at an expert level without any human intervention. In this talk we will give a brief overview of the field of GGP as well as the inner workings of CadiaPlayer, a competitive GGP agent developed at Reykjavik University and the reigning GGP champion.

Hjalti Magnússon. Turning the study of stack-sortable permutations into algorithmics.
Abstract: The study of permutation patterns began in earnest when Knuth, in the 1960's, discovered that permutations sortable by a single pass through a stack are precisely those who avoid the classical pattern 231. In 1993, West classified permutations sortable with two passes through a stack, and recently Úlfarsson classified permutations sortable with three passes. In this talk we will present an algorithm that determines when stack-sort outputs a given classical pattern and also a certain class of mesh patterns. This algorithm can be used to automate the proofs of Knuth, West and Úlfarsson.


Helga Guðmundsdóttir. Putting Theory to the Test: Distributed Connectivity in Wireless Networks.
Abstract: We consider the interaction between wireless devices that interfere with one another, using the same wireless channel for communication. We focus on the problem of constructing a communication infrastructure from scratch, for a collection of identical wireless nodes under the SINR model of wireless interference. We study a simple and fully distributed algorithm for initial connectivity, for which theoretical analysis indicates has favorable characteristics. We implemented and experimentally evaluated the algorithm on a hardware test-bed with 40 wireless modules and used computer simulations to put our theory to the test. We try to determine the extent to which the SINR model captures the important properties for wireless interference in the context of algorithms and protocols such as the one we investigate here. These experiments verify that the performance of the algorithm matches the behavior predicted by theory and we find the SINR model to be realistic in many cases. However, the theoretical framework makes a number of assumptions that abstract away inconvenient details from reality. Based on joint work with Eyjólfur I. Ásgeirsson (RU), Joseph T. Foley (RU), Magnús Már Halldórsson (RU), Sindri Magnússon (KTH, Sweden), Henning Úlfarsson (RU) and Ýmir Vigfússon (RU).


Magnús M. Halldórsson. The 2012 Gödel Award.
Abstract: This talk will celebrate the award of the Gödel Prize 2012 to three papers in algorithmic game theory and mechanism design.


Luca Aceto. The Work of Moshe Vardi, Recipient of the EATCS Award 2012.
Abstract: The European Association for Theoretical Computer Science (EATCS) annually honours a respected scientist from the theoretical computer science community with the prestigious EATCS Distinguished Achievements Award. The award is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career.
The EATCS Award 2012 has been given to Moshe Vardi, who is a member of the scientific advisory board of ICE-TCS. In this short talk, I will briefly review some of Moshe Vardi's research achievements and highlight some of the reasons why he is such an inspirational figure within the computer science community as a whole.


Please send comments and bug reports to Luca Aceto.