7^th International Conference on

Algorithms and Complexity

May 26-28, 2010 Rome, Italy

Invited speakers

Wen 26, 9.30—10.30: Resilient Algorithms and Data Structures

Giuseppe F. Italiano, University of Rome "Tor Vergata"

Abstract. Modern memory devices may suffer from faults, where some bits may arbitrarily flip and corrupt the values of the affected memory cells. The appearance of such faults may seriously compromise the correctness and performance of computations. In recent years, many algorithms for computing in the presence of memory faults have been introduced in the literature: in particular, an algorithm or a data structure is called resilient if it is able to work correctly on the set of uncorrupted values. In this invited talk I will survey recent work on resilient algorithms and data structures.

Thu 27, 9.30—10.30: Towards a Distributed Search Engine

Ricardo Baeza-Yates, Yahoo! Research

Abstract. In this invited talk we address the algorithmic problems be- hind a truly distributed Web search engine. The main goal is to reduce the cost of a Web search engine while keeping all the benefits of a cen- tralized search engine in spite of the intrinsic network latency imposed by Internet. The key ideas to achieve this goal are layered caching, on- line prediction mechanisms and exploit the locality and distribution of queries.

Thu 27, 14.00—15.00: A three pronged approach to graph colouring

Bruce Reed, McGill University

Abstract.Choosing the right problem to study, and the right tools with which to attack it are half the battle in mathematics. As Hilbert noted, each era produces its own problems. Two huge influences on the choice of problems in modern graph theory are the size of the complex networks which are now the object of study, and the development of the computer which allows for the algorithmic resolution of optimization problems on suchhuge networks.
We discuss three techniques for solving graph colouring problems on huge networks: decomposition theorems, probabilistic methods, and using solutions to the fractional relaxation of the graph colouring problem to obtain near or near-optimal colourings.
We illustrate these approaches and their combination by discussing a number of recent results on graph colouring.

Fri 28, 9.30—10.30: Mechanisms for the Marriage and the Assignment Game

Monika Henzinger, Ecole Polytechnique Federale de Lausanne

Abstract. Starting with two models fifty years ago, the discrete marriage game and the continuous assignment game, the study of stable matchings has evolved into a rich theory with applications in many areas. Most notably, it has lead to a number of truthful mechanisms that have seen a recent rejuvenation in the context of sponsored search. In this paper we survey the history of these problems and provide several links to ongoing research in the field.

Fri 28, 14.15—15.15: Deciphering the genetic components of human diseases

Eran Halperin, Tel Aviv University

Abstract. Understanding the genetic factors leading to a disease may lead almost immediately to better diagnosis and treatment of the disease. In the last few decades the scientific community has been able to pin down many mutations and other genetic variants that are correlated with human diseases. These discoveries have recently accelerated due to revolutionary improvements in sequencing and genotyping technologies. In an attempt to push the new technologies to their limits of statistical power, we are facing the challenge of designing efficient studies under budget constraints, and the challenge of accurately inferring missing and ambiguous data from noisy sequencing measurements. In this talk I will give a few examples of the challenges we are currently facing and I will present the current solutions. Particularly, I will discuss computational and statistical challenges in the analysis of studies involving families, and in studies of recently admixed populations, which are populations that came about by the mixing of two or more distant ancestral populations over a few hundred years (e.g., African Americans or Latinos).