This year, after about 7 or 8 years, I am attending again the
SOFSEM conference on 'Current Trends in Theory and Practice of Computer Science' (for the 2nd time). Maybe SOFSEM is not the most important of all the computer science conferences around, but it is rather original and has quite some history (i.e. it's tradition dates back more than 30 years...). SOFSEM means SOFtware SEMinar, and this already gives some hint about its originality. Starting from a winter lecture with only limited international attendance it has developed to an interesting mixture of lectures (given by invited speakers of significant reputation), presentations of reviewed research papers, and student paper presentations. By tradition, it's location always switches between somewhere in Slowakia and the Czech Republique and always in winter. Unfortunately, this year winter did not really show up and thus, we are sitting here in
Harrachow (a well known winter resort) without any snow. On the other hand, nice thing about this situation is that travelling this year has become much easier (because there is no snow even in the mountain areas).
This year, I am co-chairing the track 'emerging web technologies' as being one of the four SOFSEM tracks. By tradition, there is always a track 'foundations of computer science' besides of three changable tracks concering breaking topics of current interest , i.e. (in this year) 'multi-agent systems', 'emerging web technologies', and 'dependable software and systems'.
The first day on SOFSEM, after the opening note given by
Jan van Leeuwen, in which he referred to the long tradition of SOFSEM and to Czech computer science history, starts with a full day of invited lectures covering all four topics.
- Manfred Broy from TU Munich started with a presentation on 'Interaction and Realizability'. In interactive computation - in difference to sequential, atomic computation - input as well as output is not provided as a whole, but step by step while the computation continues. He pointed out that interactive behaviour can be modeled with Moore machines and introduced the term of 'realizability', which is a fundamental issue when asking whether a behaviour corresponds to a computation. 'Realizable functions' are defined as being abstractions of state machines (in a similar way as partial functions are abstractions of Turing machines) and can be used to extend the idea of computability to interactive computations.
- Andrew Goldberg followed with a talk on 'Point-to-Point Shortest Path Algorithms with Preprocessing'. To run on even small devices while at the same time covering graphs with tens of millions of nodes (as, e.g., in roadmaps for navigation devices), off course efficient algorithms are required. The traditional way is to search a ball around the starting point (as e.g. in Dijkstra's algorithm) that can be speed up by biasing the search towards to intendet target point (as e.g. in A* search, if additional information is available that provides a lower-bound on the distance to the target) or by pruning the search graph (as e.g. in ALT algorithms that precompute distances to preselected landmarks, or using 'reaches').
- Jerome Lang from IRIT (France) continued the afternoon session with a survey on 'Computational Issues in Group Decision Making', which combines 'social choice' (from economics) and AI (applications) into 'computational social choice' theory. In this new and very active discipline concepts as e.g. voting procedures, coalition formation, and fair division (from social choice), which is also important for multi-agent systems, are examined under the consideration of complexity analyses and algorithm design.
- I realized that I will be the chairman of today's last session. Thus, the summary of Remco Veltkamp's (University of Utrecht, The Netherlands) talk on 'Multimedia Retrieval Algorithms' will come with a little delay....
The presentation started with citing Marshal McLuhan's famous quote 'The medium is the message' smartly being connected to the basic definitions of multimedia retrieval. Difficult thing in multimedia retrieval is the proper understanding of the mechanisms of human perception and in connection to that the question of how to take care of it's peculiarity in information retrieval. E. g., the human visual system is famous for 'generic interpretations', i.e. sometimes we see things that are not really there, as already has been described by Wertheimer's Gestalttheorie back in 1923. Interesting fact, that some of these visual illusions do also exist for audio perception. For multimedia retrieval metrics have to be defined for computing similarities (as well as differences of multimedia objects) in an efficient way, while the algorithms dealing with multimedia retrieval have to be carefully designed according to the type of problem that is addressed (e.g., computing problem, optimization problem, decision problem, etc.). The presentation closed with a short demonstration of the music search engine Muugle that realizes the concept of 'query-by-humming'.
