Workshop on Space-Conscious Algorithms

10-15 June 2006
University of Bologna Residential Center
Bertinoro (Forlė), Italy

bertinoro
[ What the Meeting is About
| Location
| How to Reach Bertinoro
| Schedule of the Talks
| List of Participants
| Organization and Sponsorship
| Local Weather Forecast]

What the Meeting is About

Traditionally, the area of efficient algorithms has focused on speeding up solutions. Now, with increasing data sizes, there is focus on designing algorithms that need to be additionally space-conscious, that is, use linear or even sublinear space in some cases, rely on faster memory in the hierarchy more judiciously, work seamlessly with differing storage configuration in computing systems, use lossy or lossless compression to represent and manipulate datasets, etc. Motivated by this, the Algorithms community has developed new mathematical tools and theory of algorithms including external memory algorithms, synopses-based algorithms, cache-oblivous algorithms, succinct data structures and others. At the same time, there has been significant developments in the complexity theory of space-bounded computations. At the core of these are powerful randomization and approximation techniques. The workshop is aimed at bringing together the researchers in disparate areas of algorithms and theoretical computer science who have common goal of space-conscious methods. Also, the workshop will bring together limited number of researchers in other areas where space-conscious algorithms find applications.

Location

The meeting will be held in the small medieval hilltop town of Bertinoro. This town is in Emilia Romagna about 50km east of Bologna at an elevation of about 230m.  Here is a map putting it in context. It is easily reached by train and taxi from Bologna and is close to many splendid Italian locations such as Ravenna, a treasure trove of byzantine art and history, and the Republic of San Marino (all within 35km) as well as some less well-known locations like the thermal springs of Fratta Terme and the castle and monastic gardens of Monte Maggio.  Bertinoro can also be a base for visiting some of the better-known Italian locations such as Padua, Ferrara, Vicenza, Venice, Florence and Siena.

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

Talk Schedule

10
11
12
13
14
15
Sat
Sun
Mon
Tue
Wed
Thu
08.00-09.30 arrivals breakfast
09.30-10.00 Navarro Farach Raman Vitter TBA
10.00-10.30 coffee coffee coffee coffee coffee
10.30-11.00 Makinen Drineas Mahoney Lopez-Ortis TBA
11.00-11.30 Indyk Gibbons Shah TBA TBA
11.30-12.00 -- Rae Brodal Tager TBA
12.00-15.00 lunch! lunch! lunch! lunch! lunch!
15.00-15.30 Chakrabarti Gagie Strauss TBA departures
15.30-16.00 Fagerberg McGregor Cormode TBA
16.00-16.30 coffee coffee coffee coffee
16.30- open discussion open discussion open discussion open discussion

Current list of participants.

  1. Diego Arroyuelo, U. Chile.
  2. Ilaria Bordino, U. Roma "La Sapienza".
  3. Gerth Brodal, BRICS.
  4. Amit Chakrabarti, Dartmouth College.
  5. Graham Cormode, Bell Labs.
  6. Petros Drineas, RPI.
  7. Rolf Fagerberg, BRICS.
  8. Travis Gagie, U. Toronto.
  9. Phillip B. Gibbons, Intel.
  10. Roberto Grossi, U. Pisa.
  11. Mangesh Gupte, U. Rutgers.
  12. John Iacono, Polytechnic U.
  13. Piotr Indyk, MIT.
  14. Stefan Langerman, Université Libre de Bruxelles.
  15. Luigi Laura, U. Roma "La Sapienza".
  16. Alex Lopez-Ortiz, U. Waterloo.
  17. Michael Mahoney, Yahoo! Research.
  18. Veli Makinen, U. Helsinki.
  19. Andrew Mc Gregor, U. Penn.
  20. Gonzalo Navarro, U. Chile.
  21. Igor Nitto, Scuola Normale Superiore, Pisa.
  22. Seth Pettie, MPI.
  23. Greg Rae, 22by7 Labs .
  24. Rajeev Raman, U. Leicester .
  25. Kunihiko Sadakane, U. Kyushu.
  26. Rahul Shah, Purdue U..
  27. Martin Strauss, U. Michigan.
  28. Wolfgang Täger, EPO.
  29. Jeff Vitter, Purdue U.

Organization and Sponsorship

Scientific Organizing Committee Martin Farach-Colton, Rutgers University, USA
Paolo Ferragina, University of Pisa, Italy
S. Muthukrishnan, Rutgers University, USA
Local Organization
Eleonora Campori, Segreteria organizzativa CEUB.
Sponsored by BICI   Bertinoro International Center for Informatics


Maintained by Paolo Ferragina