Third ICE-TCS Theory Day

Last Friday, ICE-TCS hosted its third theory day. The programme for the event may be found here.

This year's theory day featured an inaugural professorial address delivered by Magnús M. Halldórsson, who joined my department at Reykjavík University on August 1. The addition of Magnús to our academic staff will substantially strengthen our research profile.

At the theory day, Magnús gave a talk in which he presented approximation algorithms for optimization problems when the objective function is unknown. The aim of the work he discussed during his presentation is to obtain algorithms that are guaranteed to perform reasonably well for all objective functions in the given class. He focussed on cost functions that are monotonic and concave (or, more generally, sub-additive), and presented approximation algorithms whose approximation ratio is 4 for concave functions and 6 for sub-additive ones.

Thomas Erlebach from the University of Leicester continued the "approximation theme" with a talk on network discovery problems. The work Thomas presented in his talk aims at discovering information about an unknown network (modelled as a connected undirected graph) or on verifying the correctness of network information. Thomas discussed two query models. In the former, a query at a node returns all the shortest path trees rooted at that node. In the latter, the result of a query at a node is the collection of shortest-path distances from that node. For the former type of queries, Thomas presented, for instance, a randomized O(sqroot{n log n})-competitive algorithm. For the latter query model, there is a deterministic Omega(sqroot{n}) lower bound and a randomized O(log n) lower bound. Much more can be found in the paper

Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, L. Shankar Ram:
Network Discovery and Verification
IEEE Journal on Selected Areas in Communications, Vol. 24, No. 12, December 2006, pp. 2168-2181. Special issue on Sampling the Internet: Techniques and Applications.

The afternoon session was devoted to a one-hour talk by Tommi Sottinen, our new recruit in financial mathematics, and to two 25-minute talks by Silvio Capobianco and MohammadReza Mousavi. Tommi gave an accessible introduction to the mathematics underlying financial mathematics and the Black-Scholes model. Silvio reported on recent joint work with Patrizia Mentrasti and Tommaso Toffoli, and showed us how to convert certain types of cellular automata to lattice gases. Mohammad wound up a nice scientific day by giving an accessible introduction to some recent work of his aiming at a unified framework for functional and performance analysis of processes. He proposed an approach enabling a provably sound transformation from some existing stochastic process algebras, e.g., PEPA and MTIPP, to a generic form in the mCRL2 language.

This workshop marks the beginning of a very busy year for ICE-TCS, a year leading up to ICALP 2008 in Reykjavík. I hope to see you in Reykjavík for that conference!