For many random Constraint Satisfaction Problems, we have reasonably good estimates of the largest constraint density for which there exist solutions. These estimates are obtained by non-constructive arguments such at the "second moment method". In most cases no polynomial-time algorithm is known to solve instances of these problems even at much smaller densities than the threshold for the existence of solutions. In effect, random problem instances have been considered prime examples of "hard" instances. For example, it is very easy to color a random graph using twice as many colors as its chromatic number. Yet, to date, no algorithm is known to get along with (2-ε) times chromatic number colors. I'm going to present some recent progress towards a rigorous explanation of this "hardness transition", which is based in parts on ideas from statistical physics.

Cooper, Dyer and Greenhill showed that random switch moves on 2r-regular graphs give a rapidly mixing Markov chain with uniform equilibrium distribution. This was used to model the SWAN peer-to-peer network of Holt and Bourassa (2003). Mahlmann and Schindelhauer (2005) proposed the alternative flip chain in the context of peer-to-peer networks. This was analysed by Feder, Guetz, Mihail and Saberi (2006) using Cooper, Dyer and Greenhill's result and the comparison method for Markov chains. We give a more direct analysis of the flip chain which greatly improves the mixing time estimate. We will also outline the peer-to-peer application.

Joint work with Colin Cooper and Andrew Handley

The efficiency of many discrete algorithms crucially depends on quantifying properties of large structured combinatorial configurations. We survey methods of analytic combinatorics that are simply based on the idea of associating numbers to atomic elements that compose combinatorial structures, then examining the complex geometry of the resulting functions. In this way, an operational calculus of discrete structures emerges. Applications to basic algorithms, data structures, and the theory of random discrete structures are outlined.

Efficient exploration of unknown or unmapped environments has become one of the fundamental problem domains in algorithm design. Its applications range from robot navigation in hazardous environments to rigorous searching, indexing and analysing digital data available on the Internet. A large number of exploration algorithms has been proposed under various assumptions about the capability of mobile (exploring) entities and various characteristics of the environment which are to be explored. Here we consider the "graph model", where the environment is represented by a graph of connections in which discrete moves are permitted only along its edges. Designing efficient exploration algorithms in this model has been extensively studied under a diverse set of assumptions, e.g., directed vs undirected graphs, anonymous nodes vs nodes with distinct identities, deterministic vs probabilistic solutions, single vs multiple agent exploration, as well as in the context of different complexity measures including the time complexity, the memory consumption, and the use of other computational resources such as tokens and messages. In this talk the emphasis is on memory efficient exploration of anonymous graphs. We discuss in greater detail three approaches: "random walk", "Propp machine" and "basic walk", reviewing major relevant results, presenting recent developments, and commenting on directions for further research.

An oblivious routing protocol makes its routing decisions independent of the traffic in the underlying network. This means that the path chosen for a routing request may only depend on its source node, its destination node, and on some random input. In spite of these serious limitations it has been shown that there are oblivious routing algorithms that obtain a polylogarithmic competitive ratios w.r.t. the congestion in the network (i.e., maximum load of a network link).

In this talk I will present a new hierarchical decomposition technique that leads to good oblivious routing algorithms. This decomposition can also be used as a generic tool for solving a large variety of cut based problems in undirected graphs. In particular, it can e.g. be used to design an approximation algorithm for the Minimum Bisection Problem that improves upon the previously known approximation guarantees.

Extensive games with perfect recall are a fundamental model of noncooperative game theory. They are game trees where players may have imperfect information about the game state, modeled by "information sets" due to Kuhn (1953). The standard rationality assumption of perfect recall asserts that a player never forgets what he knew or did earlier.

We present the first equilibrium concept that can be computed in polynomial time for extensive games with any number of players, and chance moves. The corresponding algorithm extends the method by Papadimitriou and Roughgarden (2005, 2008) for finding one "correlated equilibrium" in succinctly representable games.

The main problem of extensive games is that a player has exponentially many pure strategies. In Nash equilibria, this can be remedied by "behaviour strategies" where choices are randomised locally and without correlation across information sets. We extend this concept to correlated equilibria by "delaying" the recommended actions in a correlated equilibrium until the respective decision points are reached.

The talk will focus on explaining the problem and the new solution concept of "extensive form correlated equilibrium", rather than the technical aspects of the algorithm.

Joint work with Wan Huang (LSE).

Extended abstract to appear in WINE2008.