# Invited Speakers at ICALP 2010

**Pierre Fraigniaud**(CNRS and Univ. Paris Diderot): Informative Labeling Schemes (Friday 9, 9h - 10h)**Jean Goubault-Larrecq**(ENS Cachan and LSV): Noetherian Spaces in Verification (Wednesday 7, 9h - 10h)**Burkhard Monien**(Univ. Paderborn): Local Search: Simple, Successful, but Sometimes Sluggish (Saturday 10, 9h - 10h)**Joel Ouaknine**(Oxford Univ. Computing Lab.): Towards a Theory of Time-Bounded Verification (Thursday 8, 14h - 15h)**Roger Wattenhofer**(ETH Zurich): Physical Algorithms (Tuesday 6, 9h - 10h)**Emo Welzl**(ETH Zurich): When Conflicting Constraints Can be Resolved -- the Lovasz Local Lemma and Satisfiability (Thursday 8, 9h - 10h)

### 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.