****************** * * * F U N ' 9 8 * * * ******************* FUN with Algorithms THE ISLAND OF ELBA, ITALY June 18 - 20, 1998 Sponsored by C.N.R. Carleton University Universita' di Pisa Universita' di Siena For more information see http://www.di.unipi.it/fun98 or send mail to fun98@di.unipi.it ********************************************************************** ``...pleasure has probably been the main goal all along. But I hesitate to admit it, because computer scientists want to mantain their image as hard-working individuals who deserve high salaries. Sooner or later society will realise that certain kinds of hard work are in fact admirable even though they are more fun than just about anything else.'' (KNUTH D.E., The Stanford Graph Base. A Platform for Combinatorial Computing) *********************************************************************** GENERAL INFORMATION FUN '98 concerns, to a general extent, the use, design and analysis of algorithms and data structures; in particular of interest are results that provide amusing, witty but nonetheless original and scientifically profound contributions to the areas of combinatorial algorithms, randomized algorithms, parallel algorithms, distributed algorithms, geometrical algorithms, and numerical algorithms. The workshop will take place in a resort of the Island of Elba (Isola d'Elba), famous for its white sand, deep blue sea and fascinating nature. Ancient Romans were the first to choose the island as one of their favourite places to spend their holidays. The island became the small kingdom of Napoleon as witnessed by some local, historical places. In June, typical temperatures are in the mid-20's C (upper-70's F), cooling down in the evening. TRANSPORTATION The most convenient airport to reach the Island of Elba is Rome, serviced by the major world airlines. Roma Termini, the main train station, can be easily reached from Fiumicino Airport by a shuttle train (Lit. 10,000). It then takes about 4-5 hours to reach the Island of Elba. From Roma Termini, Campiglia Marittima can be reached by train in about 2:30 hours. At this point, Piombino Scalo can be reached in about 30 minutes by commuting in Campiglia Marittima, where a ferry boat is available to go to Portoferraio (Isola d'Elba) in about 1 hour. Alternatively, an air-craft takes 30 minutes. More information is available at the Internet sites www.fs-on-line.com for trains and www.luda.livorno.it/toremar for ferries. As far as the latter are concerned, early registration is strongly recommended for those willing to bring a car. CURRENCY EXCHANGE Approximate Exchange Rate: USD 1 = Lit. 1,800. Exchange bureaus can be found at local banks; banks are closed from 1:30 p.m. to 2:30 p.m. and after 3:30 p.m. on weekdays and throughout weekends. ACCOMODATIONS Blocks of rooms have been reserved at the hotels listed below. Rooms and rates are guaranteed until May 22. Thereafter, reservations are subject to availability. As June is peak season in the Island of Elba for touristic events, early reservations are strongly recommended. The prices listed below are intended to be per person, except for Camping Acquaviva. Hotel Le Picchiaie****, I-57037 Portoferraio, Isola d'Elba, Tel: +39 565 933072/110, Fax: +39 565 933186, Lit. 165,000 (in single room), Lit. 135,000 (in double room), breakfast and dinner included. This is the workshop site. Internet: www.ouverture.it/elba/alberghi/picc_it.htm Hotel Garden***, I-57037 Portoferraio, Isola d'Elba, Tel: +39 565 933043, Fax: +39 565 933268, Lit. 145,000 (in single room), Lit. 120,000 (in double room), breakfast and dinner included. At walking distance from the workshop site. Internet: www.ouverture.it/elba/alberghi/gard_it.htm Hotel Lacona***, I-57031 Capoliveri, Isola d'Elba, Tel: +39 565 964050/054, Fax: +39 565 964189, Lit. 145,000 (in single room), Lit. 120,000 (in double room), breakfast and dinner included. Reasonably far from the workshop site, but near the beach! Internet: www.ouverture.it/elba/alberghi/laco_it.htm Camping Acquaviva, I-57037 Portoferraio, Loc. Acquaviva, Isola d'Elba, Tel: +39 565 930674, Fax: +39 565 915592. Daily price per person Lit. 12,500 plus Lit. 13,000 for the tent. Alternatively, daily apartment rental at Lit. 130,000 (4 persons) and Lit. 150,000 (5 persons). Special prices for groups of at least 20 persons. Pretty far from the workshop site. Internet: www.ouverture.it/elba/campeggi/acquaviv.htm All rates include taxes. Advance payment is not required and major credit cards are accepted by all of the hotels. When making the reservation, please remember to identify yourself as a FUN '98 attendee. Reservations by fax have to be confirmed by a fax reply. LOCATION OF EVENTS Workshop and lodging facilities are all within 15 minutes walk in the Island of Elba. The workshop site is Hotel Residence Le Picchiaie. A shuttle will be available to connect the lodging facilities to the workshop site. *********************************************************************** FUN '98 REGISTRATION FORM Name (first, last): Name tag should read: Affiliation: Address: Phone: Fax: Internet address: Check your dietary preference: Vegetarian No Restriction Please indicate any special needs: Workshop registration includes the proceedings, welcome reception, lunches on Thursday, Friday and Saturday, banquet on Friday evening, and coffee breaks. Proceedings and workshop banquet are not included in student registration fees. The deadline for early registration is May 31, 1998. (But register with hotels before May 22.) Please circle selection: Registration: EARLY LATE Regular $280 (Lit. 500,000) $330 (Lit. 590,000) Student $100 (Lit. 180,000) $150 (Lit. 220,000) Additional Tickets: NUMBER AMOUNT Lunch ($18 or Lit. 30,000 each) ________ __________ Banquet ($28 or Lit. 50,000 each) ________ __________ TOTAL: *********************************************************************** Please include a completed registration form with your payment. No credit cards please. Fees can be paid by bank draft or check (in U.S. Dollars or in Italian Lire) made payable to the bank account: Elba Promotion, Cassa di Risparmi di Livorno, Filiale di Portoferraio (Li), Italy account no. 35083582. and mailed to: Elba Promotion, Calata Italia 26, I-57037 Portoferraio (Li) Tel.: +39 565 960157, Fax.: +39 565 917632 Internet: elbapro@ouverture.it FUN '98 PROCEEDINGS The proceedings for FUN '98 will be published by Carleton Scientific, and will be distributed shortly after the workshop. *********************************************************************** F U N ' 9 8 P R O G R A M *********************************************************************** Thursday, June 18, 1998 8:00 Workshop Registration (Hotel Residence Le Picchiaie) INVITED TALK 9:00 Quantum Search: Can We Read the Wavefunction? Franco Preparata, Brown Univ., USA 9:50 Coffee Break SESSION 1 10:00 The Chords' Problem Y. Gerard, A Daurat, Univ. de Ceseaux, France; M. Nivat, Univ. Denis Diderot , France 10:30 A Theory of Computing Symposia Avrim L. Blum, Carnagie mellon Univ., USA; Prabhakar Raghavan, IBM Almaden, USA 11:00 Cutting Circles and Squares into Equal Area Pieces Prosenjit Bose, Carleton Univ., Canada; Jurek Czyzowicz, Univ. du Quebec a Hull, Canada; Evangelos Kranakis, Danny Krizanc, Anil Maheshwari, Carleton Univ., Canada 11:30 Coffee Break INVITED TALK 11:40 Area Efficient Layouts of the Batcher Sorting Networks Shimon Even, Technion Univ., Israel 12:30 Lunch (Le Picchiaie) INVITED TALK 14:30 Half-a-Century of Computer Chess: The Longest Running Experiment in Knowledge Engineering Jurg Nievergelt, ETH Zurich, Switzerland 15:20 Coffee Break SESSION 2 15:30 SOKOBAN is PSPACE-complete Joe Culberson, Univ. of Alberta, Canada 16:00 A Strip-Like Tiling Algorithm Donatella Merlini, Renzo Sprugnoli, M. Cecilia Verri, Univ. di Firenze, Italy 16:30 The Passport Control Problem or How to Keep an Unstable Service System Load Balanced Alon Itai, Michael Rodeh, Hadas Shachnai, Technion Univ., Israel *********************************************************************** Friday, June 19, 1998 INVITED TALK 9:00 A Model for Cycle-Stealing in NOWs: Properties and Problems Arnold Rosenberg, Univ. of Massachusetts, USA 9:50 Coffee Break SESSION 3 10:00 On the Collapse of the q-Gram Filtration Erkki Sutinen, Univ. of Helsinki, Finland; Wojciech Szpankowski, Purdue Univ., USA 10:30 Making the Analysis of complicated Algorithms Fun: A Manifesto for the Computational Method Steve Seiden, Graz Univ., Austria 11:00 Filtering Near-Duplicate Documents Andrei Z. Broder, Digital Palo Alto, USA 11:30 Coffee Break INVITED TALK 11:40 From Algorithm to Program Kurt Mehlhorn, MPI of Saarbr\"ucken, Germany 12:30 Lunch (Le Picchiaie) INVITED TALK 14:30 Algorithmic Aspects of Dynamic Coalitions and Monopolies in Graphs David Peleg, Weizmann Institute, Israel 15:20 Coffee Break SESSION 4 15:30 Heap Games and Numeration Systems Aviezri Fraenkel, Weizmann Inst., Israel 16:00 Robust Matching Rafael Hassini, Shlomi Rubinstein, Tel Aviv Univ., Israel 16:30 Continuos Max-Min Tree Partitioning Ronald Becker, Univ. of Cape Town, South Africa; Bruno Simone, Univ. of Rome, Italy; Yen-I Chiang, Univ. of Cape Town, South Africa 20:00 Banquet *********************************************************************** Saturday, June 20, 1998 INVITED TALK 9:00 Algorithms, Deities, and Ordinary People Fabrizio Luccio, Univ. of Pisa, Italy 9:50 Coffee Break SESSION 5 10:00 FUN with Implementing Algorithms Rudolf Fleischer, MPI of Saarbr\"ucken, Germany 10:30 Noah's Bagels -- Some Combinatorial Aspects Tami Tamir, Hadas Shachnai, Technion Univ., Israel 11:00 What if Mathematicians Were Asked to Defuse Bombs Paolo Boldi, Massimo Santini, Sebastiano Vigna, Univ. of Milan, Italy 11:30 Coffee Break 11:40 A Note on an Origami Magic Trick Marshall Bern, Xerox, Palo Alto, USA; David Eppstein, Univ. of California, USA; Farry Hayes, Placeware Inc., USA 12:10 Searching with a Constant Rate of Malicious Lies Alberto Pedrotti, SNS Pisa, Italy; 12:30 Lunch (Le Picchiaie) SPECIAL SESSION 15:00 FUN Session *********************************************************************** FUN '98 ORGANIZATION WORKSHOP CHAIRS Elena Lodi, Univ. of Siena, Italy Linda Pagli, Univ. of Pisa, Italy Nicola Santoro, Carleton Univ., Canada PROGRAM COMMITTEE Giorgio Ausiello, Univ. of Rome, Italy Shimon Even, Technion Univ., Israel Zvi Galil, Columbia Univ., USA Fabrizio Luccio, Univ. of Pisa, Italy Kurt Mehlhorn, MPI of Saarbr\"ucken, Germany Jurg Nievergelt, ETH Zurich, Switzerland David Peleg, Weizmann Institute, Israel Franco Preparata, Brown Univ., USA Arnold Rosenberg, Univ. of Massachusetts, USA LOCAL ARRANGEMENTS COMMITTEE Gabriele Lenzini, Univ. of Pisa Giuseppe Prencipe Univ. of Pisa SPONSORS The following institutions have provided generous support: - C.N.R. - Carleton University - Universita' di Pisa - Universita' di Siena ***********************************************************************