ADS 2003 Algorithms and Data Structures June 22-27, 2003 University of Bologna Residential Center Bertinoro (Forlì), Italy

[ What the Meeting is About
| Seminar Schedule
| Important Dates
| Location
| How to Reach Bertinoro
| Accomodation
| List of Participants and snapshots
| Information for Ph.D. Students
| Abstracts
| Organization and Sponsorship
| Local Weather Forecast]

What the Meeting is About

Program

Monday, June 23
08:30-09:30	Breakfast
09:50-10:00	Welcome address
10:00-10:45	Frank Schulz (University of Konstanz) "Using multi-level graphs for fast single-pair shortest-path computation"
10:45-11:15	Coffee break
11:15-12:00	Roberto Grossi (Universita' di Pisa) "Efficient implicit data structures for the dictionary problem"
12:00-14:30	Lunch
14:30-15:15	John Iacono (Polytechnic University) "Input-sensitive data structures"
15:15-16:00	Stefan Langerman (Universite Libre de Bruxelles) "Input-sensitive data structures" (cont'd)
16:00-16:30	Coffee break
16:30-19:30	Time for meetings and discussions
19:30	Dinner (Altopalato)

Tuesday, June 24
08:30-09:30	Breakfast
10:00-10:45	Amos Fiat (Tel Aviv University) "Some issues regarding peer to peer networks"
10:45-11:15	Coffee break
11:15-12:00	Andrew Goldberg (Microsoft Research) "Competitive auctions"
12:00-14:30	Lunch
14:30-15:15	Valerie King (University of Victoria) "Complexity of reconstructing phylogenetic trees"
15:15-16:00	Giancarlo Mauri (Università di Milano - Bicocca) "Pattern discovery in nucleotide sequences: methods and data structures"
16:00-16:30	Coffee break
16:30-17:30	Problems session
17:30-19:30	Time for meetings and discussions
19:30	Dinner

Wednesday, June 25
08:30-09:30	Breakfast
10:00-10:45	Giuseppe F. Italiano (Universita' di Roma "Tor Vergata) "A new approach to dynamic all pairs shortest paths"
10:45-11:15	Coffee break
11:15-12:00	Camil Demetrescu (Universita' di Roma "La Sapienza") "An experimental analysis of dynamic all pairs shortest paths algorithms"
12:00-14:30	Lunch
14:30	Excursion to Ravenna

Thursday, June 26
08:30-09:30	Breakfast
10:00-10:45	Gerth S. Brodal (University of Aarhus) "Cache oblivious sorting"
11:15-12:00	Lars Arge (Duke University) "Cache-oblivious orthogonal range searching"
12:00-14:30	Lunch
14:30-15:15	Haim Kaplan (Tel Aviv University) "Inverse range searching with priorities"
15:15-15:45	Coffee break
15:45-16:30	Marco Pellegrini (IIT - CNR) "Internet packet filtering on any number of attributes via multi-dimensional point stabbing"
16:30-16:35	Adjourn
19:30	Dinner

Important Dates

Location

Bertinoro itself is picturesque, with many narrow streets and walkways winding around the central peak.  The meeting will be held in a redoubtable ex-Episcopal fortress that has been converted by the University of Bologna into a modern conference center with computing facilities and Internet access.  From the fortress you can enjoy a beautiful the vista that stretches from the Tuscan Apennines to the Adriatic coast.

How to Reach Bertinoro

Directions are available here.

Accomodation

Accomodation costs are 105 EUR (single) or 95 EUR (sharing a double) per day, including breakfast, meals, and coffee breaks. The cost for accompanying persons is 52 EUR (single) or 43 EUR (sharing a double) per day, including breakfast and lunches.

List of participants and snapshots

	Lars Arge Gerth Brodal Camil Demetrescu Pompeo Faruolo Amos Fiat Irene Finocchi Andrew Goldberg Sara Gradara Roberto Grossi John Iacono Giuseppe Italiano Haim Kaplan Valerie King Stefan Langerman Giancarlo Mauri Marco Pellegrini Frank Schulz Gabriele Venturi

Information for Ph.D. Students

Ph.D. students interested in attending the meeting can contact Camil Demetrescu or Giuseppe F. Italiano.

Organization and Sponsorship

Scientific Organizing Committee	Camil Demetrescu University of Rome "La Sapienza"
	Giuseppe F. Italiano, University of Rome "Tor Vergata"
Local Organization
	Andrea Bandini, Elena Della Godenza, Centro Congressi di Bertinoro
Sponsored by		BICI   Bertinoro International Center for Informatics

Abstracts (partial list)

Cache-oblivious sorting. Gerth S. Brodal (University of Aarhus)

An experimental analysis of dynamic all pairs shortest paths algorithms. Camil Demetrescu (Università di Roma "La Sapienza")

Some issues regarding peer to peer networks. Amos Fiat (Tel Aviv University) Random data structures formed in peer to peer networks are useful for a variety of purposes, increasing the resiliency of the network, efficient search and anonymity are three examples. I'll describe some recent and less recent work on this subject.

Competitive auctions. Andrew V. Goldberg (Microsoft Research) Recent trends, such as proliferation of digital goods and the emergence of the Internet, have led to new dynamic pricing problems. Traditionally studied by Economists and Game Theorists, these problems have recently attracted attention of Computer Scientists. Auctions are widely used dynamic pricing mechanisms. This talks is a survey of recent work on competitive auctions. Classical mechanism design works in Bayesian setting: mechanisms assume that inputs come from a known distribution and are designed to maximize expectation of a desired parameter with respect to this distribution. We take the worst-case analysis approach more common in Computer Science and motivated by on-line algorithms. Our competitive auctions combine two conflicting goals: maximizing seller's revenue and encouraging buyers to bid their true utility (i.e., these auctions are truthful). In the competitive auction framework, one compares revenue of a truthful auction to that of an optimal auction that need not be truthful. We show that optimal single-price auctions are the right benchmark for comparison. We also show that, for a reasonable class of auctions, no deterministic auction is competitive and randomized competitive auctions exist. We first consider auctions for digital goods. In this context, we develop techniques for design and analysis of competitive auctions. These techniques include random sampling and consensus revenue estimate. Then we discuss extensions of these techniques to more problems. (Joint work with Amos Fiat, Jason Hartline, Anna Karlin, Andrew Wright)

Efficient implicit data structures for the dictionary problem. Roberto Grossi (Università di Pisa) In this talk we discuss some implicit data structures for the classical dictionary problem, analyzing their complexity both in the RAM model and in the hierarchical-memory model. No auxiliary space is needed as implicit data structures are entirely encoded by a suitable permutation of the keys in a contiguous area of the memory. In particular, we address the question whether using extra space in solving the dictionary problem in an unbounded universe gives more computational power than just using the space merely required by the keys, and how data ordering can help in this task. (The results presented here are based on joint papers with Gianni Franceschini and on a paper with Gianni Franceschini, Ian Munro and Linda Pagli)

Input-sensitive data structures. John Iacono (Polytechnic University) and Stefan Langerman (Université Libre de Bruxelles) One would like to take advantage of the fact that real-world access sequences often have patterns that intelligently designed systems can make use of, even though the exact distribution of operations is seldom not known in advance. Still, there is often reason to believe that the stream of queries and updates arriving at such systems is far from random. We will present theory of what we call input-sensitive behavior of query-based data structures. The objective of input-sensitive data structures and input-sensitive analysis is to create data structures and algorithms whose runtime is expressed as a function of the patterns that occur in the input, with the goal of speeding up the performance, relative to input sequences that exhibit no favorable patters, or are completely random. We will present an overview of input sensitive structures and techniques. We will then present the results of our recent work to develop new input sensitive structures for dictionaries, heaps and geometric problems. John Iacono will present the fundamental data structures while Stefan Langerman will present our geometric results. (Joint work with Erik Demaine)

Inverse range searching with priorities. Haim Kaplan (Tel Aviv University) (Joint work with Eyal Molad and Robert E. Tarjan)

Complexity of Reconstructing Phylogenetic Trees. Valerie King (University of Victoria) A phylogenetic tree is an unrooted tree with weighted edges whose leaves are labeled by distinct species. The distance between a pair of species is the sum of the weights on the path between the species. The phylogenetic tree reconstruction problem is to reconstruct this tree given an oracle which outputs the distance between a given pair of species. Now, we suppose that if the oracle outputs a distance greater than a bound p, the distance information is considered unreliable and useless. This model more closely captures assumptions about distances between species as determined by DNA comparisons, based on common models of evolution. In particular, the longer the DNA sequence, the larger the parameter p. We prove lower bounds in this p-bounded model and in the original model, and also give the first o(n^2) algorithm to reconstruct trees based on DNA distance data. (Joint work with Li Zhang and Yunhong Zhou, at HP Labs).

A new approach to dynamic all pairs shortest paths. Giuseppe F. Italiano (Università di Roma "Tor Vergata")

Pattern discovery in nucleotide sequences: methods and data structures. Giancarlo Mauri (Università degli Studi di Milano - Bicocca) In the last few years, molecular biology has produced a large amount of data, mainly in the form of sequences, that is strings over an alphabet of four (DNA and RNA sequences) or twenty symbols (proteins). For computational biologists the main challenge is now to produce efficient tools for the analysis and the comparison of the sequences. In this talk, I will introduce and briefly discuss some central problems, and present an algorithm that finds repeated substrings in a DNA sequence or common substrings in a set of sequences. The occurrences of substrings can be approximate, that is, they can differ up to a given number of mismatches. The output of the algorithm is then sorted according to different statistical measures of significance.

Internet packet filtering on any number of attributes via multi-dimensional point stabbing. Marco Pellegrini (IIT - CNR) Internet and Intranet packet classification and filtering is governed by sets of rules, each rule specifying the range of applicability for each packet attribute (for example source address number, destination address number, source port, destination port, etc..) a priority and an action. David Eppstein and Muthu Muthukrishnan in SODA 2001 have shown that, with reasonable assumptions, the problem of finding the rule applicable to the incoming packet can be solved in the RAM model in optimal time O(1) using storage O(n^{1+epsilon}) for any real parameter epsilon > 0 on a database of n rules. This result is restricted to rules with two attribute ranges and an extension to the multi-attribute case is left as an open problem. Here we show that the same asymptotic complexity bound holds for any fixed number d of attributes. Moreover the data structure is dynamic and has low preprocessing time. As a corollary of the techniques used, we also show that, under the same general assumptions, orthogonal range counting queries over a set of n points with bounded integer coordinates can be answered in time O(1) in any fixed dimension d using storage O(n^{1+epsilon}).

Using multi-level graphs for fast single-pair shortest-path computation. Frank Schulz (University of Konstanz) A so-called Multi-Level Graph is constructed by hierarchically decomposing a given graph: The node-set is thinned out step by step, which yields a hierarchy of the remaining connected components. Further, edges of shortest-path length are added between certain nodes that are removed in one step. Given a single-pair shortest-path query the Multi-Level Graph data structure allows to define a (sub-)graph in which the shortest path has the same length as in the original graph. The basic idea is that this subgraph is much smaller than the original graph, and thus can improve the running time of any shortest path algorithm for solving the query. The crucial question is how much faster a query can be solved depending on the building time and space consumption of the Multi-Level Graph data structure. In this talk preliminary results of a both theoretical and experimental analysis are shown, using on the one hand specific random graphs and, on the other hand, real-world data.

Maintained by Camil Demetrescu - Last updated: Jun 26, 2003