Invited Speakers at ICALP 2010

Informative Labeling Schemes

Pierre Fraigniaud (CNRS and Univ. Paris Diderot)

Network representations play an important role in many domains of computer science, ranging from data structures and graph algorithms, to parallel and distributed computing, and communication networks. Traditional network representations are usually global in nature. That is, in order to retrieve useful information, one must access a global data structure representing the entire network, even if the desired information is solely local, pertaining to only a few nodes. In contrast, the notion of informative labeling schemes suggests the use of a local representation of the network. The principle is to associate a label with each node, selected in a way that enables to infer information about any two nodes directly from their labels, without using any additional sources of information. Hence in essence, this method bases the entire representation on the set of labels alone. Obviously, labels of unrestricted size can be used to encode any desired information, including in particular the entire graph structure. The focus is thus on informative labeling schemes which use labels as short as possible. This talk will introduce the notion of informative labeling scheme to the audience, and will survey some of the important results achieved in this context. In particular, we will focus on the design of compact adjacency-, ancestry-, routing-, and distance-labeling schemes for trees. These schemes find applications in various contexts, including the design of small universal graphs, and the design of small universal posets.

Noetherian Spaces in Verification

Jean Goubault-Larrecq (ENS Cachan and LSV)

Noetherian spaces are a topological concept that generalizes well quasi-orderings. We explore applications to infinite-state verification problems, and show how this stimulated the search for infinite procedures à la Karp-Miller.

Local Search: Simple, Successful, but Sometimes Sluggish

Burkhard Monien (Univ. Paderborn)

In this paper, we survey the research on the complexity of computing locally optimal solutions. We revisit well-known and successful local search heuristics and present results on the complexity of the frequently used standard local search algorithm for various problems. Here, our focus in on worst case, average case, and smoothed complexity along with the existence of sequences of improving steps of exponential length. For a more theoretical investigation, we revisit the framework of PLS and mostly concentrate on the research on CongestionGames, which sparked the interconnection between local search and game theory. We conclude by stating various open problems.

Towards a Theory of Time-Bounded Verification

Joel Ouaknine (Oxford Univ. Computing Lab.)

We propose a theory of time-bounded verification for real-time systems, in which verification queries are phrased over time intervals of fixed, bounded duration. We argue that this theory is both pertinent, in that it is fully adequate to handle a large proportion of `real-world' real-time systems and specifications; and effective, in that the restriction to bounded time domains reclaims as decidable several of the key decision problems of unbounded real-time verification. Finally, we discuss several directions of ongoing and future work.

Physical Algorithms

Roger Wattenhofer (ETH Zurich)

This talk is intending to encourage research in ''physical algorithms''. The area of physical algorithms deals with networked systems of active agents. These agents have access to limited information for varying reasons; examples are communication constraints, evolving topologies, various types of faults and dynamics. The networked systems we envision include traditional computer networks, but also more generally networked systems, such as social networks, highly dynamic and mobile networks, or even networks of entities such as cars or ants. In other words, the world is becoming algorithmic, and we need the means to analyze this world!

When Conflicting Constraints Can be Resolved -- the Lovász Local Lemma and Satisfiability

Emo Welzl (ETH Zurich)

The general theme underlying the talk is the following question: Given a set of constraints, how much interleaving of these constraints (relative to how serious these constraints are) is necessary so that all of them cannot be satisfied simultaneously?
For a concrete setting we consider boolean formulas in conjunctive normal form (CNF), where the clauses play the role of constraints. If all clauses are large, it needs many clauses to obtain an unsatisfiable formula; moreover, these clauses have to interleave. We review quantitative results for the amount of interleaving required, many of which rely on the Lovász Local Lemma, a probabilistic lemma with many applications in combinatorics.
In positive terms, we are interested in simple combinatorial conditions which guarantee for a CNF formula to be satisfiable. The criteria obtained are nontrivial in the sense that even though they are easy to check, it is by far not obvious how to compute a satisfying assignment efficiently in case the conditions are fulfilled; until recently, it was not known how to do so. It is also remarkable that while deciding satisfiability is trivial for formulas that satisfy the conditions, a slightest relaxation of the conditions leads us into the territory of NP-completeness.
This is a survey with recent results by Heidi Gebauer, Robin Moser, Dominik Scheder, and Gabor Tárdos, among others.


Conference Information


Blix theme adapted by David Gilbert, powered by PmWiki