From the airport: A taxi from the airport to either hotels or University will cost abou= t CHF
From hotels to the University: It is a 10 minute walk from the first two hotels. You may cross the r= iver via either the Pont des Bergues or Pont de la Machine and then take R= ue de la Corraterie to Place Neuve. From the other hotel is a very short wa= lk, see
ICALP' 2000 Program, Registration and Practical Information Sunday July 9th Registration Opens Late Afternoon -------------------------------------------------------------------= ----- Monday, July 10th 9:00 - 10:00 INVITED TALK Game Semantics: Achievements and Prospects Samson Abramsky 10:00 - 10:50 SESSION 1 Clique is hard to approximate within n*(1-o(1)) Lars Engebretsen, Jonas Holmerin Approximating the independence number and the chromatic number in expected polynomial time Michael Krivelevich, Van Vu -------------------------------------------------------------------= ----- 10:00 - 10:50 SESSION 2 Closed Types as a Simple Approach to Safe Imperative Multi-Stage Program Cristiano Calcagno, Eugenio Moggi, Walid Taha A Statically Allocated Parallel Functional Language Alan Mycroft, Richard Sharpu -------------------------------------------------------------------= ----- (Coffee Break 10:50 - 11:10) -------------------------------------------------------------------= ----- 11:10 - 12:25 SESSION 1 An Optimal Minimum Spanning Tree Algorithm Seth Pettie, Vijaya Ramachandran Improved shortest paths on the word RAM Torben Hagerup Improved algorithms for finding level ancestors in dynamic trees Stephen Alstrup, Jacob Holm -------------------------------------------------------------------= ----- 11:10 - 12:25 SESSION 2 Lax Logical Relations Gordon Plotkin, John Power, Donald Sannella, Robert Tennent Reasoning about Idealized Algol Using Regular Languages Dan R. Ghica, Guy McCusker The measurement process in domain theory Keye Martin -------------------------------------------------------------------= ----- (Lunch 12:30 - 14:30) -------------------------------------------------------------------= ----- 14:30 - 15:30 INVITED TALK Graph Transformation as Unifying Formal Framework for System Modeling and Model Evolution Gregor Engels 15:30 - 16:20 SESSION 1 Monotone Proofs of the Pigeon Hole Principle Albert Atserias, Nicola Galesi, Ricard Gavalda Homogenization and the Polynomial Calculus Josh Buresh-Oppenheim, Matt Clegg, Russell Impagliazzo, Toniann Pitassi -------------------------------------------------------------------= ----- 15:30 - 16:20 SESSION 2 Fully-abstract Statecharts Semantics via Intuitionistic Kripke Structures Gerald L=FCttgen, Michael Mendler Algebraic Models for Contextual Nets Roberto Bruni, Vladimiro Sassone -------------------------------------------------------------------= ----- (Coffee Break 16:20 - 16:40) -------------------------------------------------------------------= ----- 16:40 - 17:30 SESSION 1 Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems Beate Bollig, Ingo Wegener Measures of Nondeterminism in Finite Automata Juraj Hromkovic, Juhani Karhum=E4ki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert -------------------------------------------------------------------= ----- 16:40 - 17:30 SESSION 2 LTL is expressively complete for Mazurkiewicz traces Volker Diekert, Paul Gastin An automata-theoretic completeness proof for Interval Temporal Logic B. C. Moszkowski -------------------------------------------------------------------= ----- (Welcome reception 18:00) -------------------------------------------------------------------= ----- Tuesday, July 11th 9:00 - 10:00 INVITED TALK Which NP-hard optimization problems admit non-trivial efficient approximation algorithms? Johan Haastad 10:00 - 10:50 SESSION 1 Deterministic algorithms for k-SAT based on covering codes and local search Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Sch=F6ning Closest Vectors, Successive Minima and Dual HKZ-Bases of Lattices Johannes Bl=F6mer ----------------------------------------------------------------= ---- 10:00 - 10:50 SESSION 2 Variable Independence, Quantifier Elimination, and Constraint Representations Leonid Libkin Constraint Satisfaction Problems and Finite Algebras Andrei Bulatov, Andrei Krokhin, Peter Jeavons ----------------------------------------------------------------= ---- (Coffee Break 10:50 - 11:10) ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 1 An optimal online algorithm for bounded space variable-sized bin packing Steven S. Seiden Resource augmentation for online bounded space bin packing J=E1nos Csirik, Gerhard Woeginger Optimal projective algorithms for the list update problem Christoph Amb=FChl, Bernd G=E4rtner, Bernhard von Stengel ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 2 Efficient Verification Algorithms for One-Counter Processes Antonin Kucera On the Complexity of Bisimulation Problems for Basic Parallel Processes Richard Mayr Decidable first-order transition logics for PA-processes D. Lugiez, Ph. Schnoebelen ----------------------------------------------------------------= ---- (Lunch 12:30 - 14:30) ----------------------------------------------------------------= ---- 14:30 - 15:30 INVITED TALK Non Interference for Analysis of Cryptographic Protocols Roberto Gorrieri 15:30 - 16:20 SESSION 1 Average bit-complexity of Euclidean algorithms Ali Akhavi, Brigitte Vall=E9e Planar maps and Airy phenomena Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Mich=E8le Soria ----------------------------------------------------------------= ---- 15:30 - 16:20 SESSION 2 Analysing Input Output Capabilities of Mobile Processes with a Generic Type System Barbara K=F6nig Information Flow vs. Resource Access in the Information Asynchronous Pi-Calculus Matthew Hennessy, James Riely ----------------------------------------------------------------= ---- (Coffee Break 16:20 - 16:40) ----------------------------------------------------------------= ---- 16:40 - 17:40 AWARD TALK Past, Present and Future of TCS Richard Karp ----------------------------------------------------------------= ---- 17:40 EATCS General Assembly (Wine and cheese ) ----------------------------------------------------------------= ---- Wednesday, July 12th 9:00 - 10:00 INVITED TALK Alteration Verification Diagrams Zohar Manna 10:00 - 10:50 SESSION 1 Necessary and sufficient assumptions for non interactive zero knowledge proofs of knowledge for all NP relations Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano Computational PCP: Short one-round proofs for NP W. Aiello, S. Bhatt, R. Ostrovsky, S. Rajagopalan ----------------------------------------------------------------= ---- 10:00 - 10:50 SESSION 2 A New Unfolding Approach to LTL Model Checking Javier Esparza, Keijo Heljanko Reasoning about message passing in finite state environments B. Meenakshi, R. Ramanujam ----------------------------------------------------------------= ---- (Coffee Break 10:50 - 11:10) ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 1 Extended notions of security for multicast public key cryptosystems Olivier Baudron, David Pointcheval, Jacques Stern One-round secure computation and secure autonomous mobile agents Christian Cachin, Jan Camenisch, Joe Kilian, Joy M=FCller Round-optimal and abuse free multi-party contract signing Birgit Baum-Waidner, Michael Waidner ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 2 On the centralizer of a finite set Juhani Karhum=E4ki, Ion Petre On the power of tree-walking automata Frank Neven, Thomas Schwentick Determinization of transducers over infinite words Marie-Pierre B=E9al, Olivier Carton ----------------------------------------------------------------= ---- (Lunch 12:30 - 14:30) ----------------------------------------------------------------= ---- (City Tours and Excursion 14:30) ----------------------------------------------------------------= ---- Thursday, July 13th 9:00 - 10:00 INVITED TALK Graph Algorithms and Constraint Programming Kurt Mehlhorn 10:00 - 10:50 SESSION 1 Scalable secure storage when half the system is faulty Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern Dual-bounded hypergraphs: Generating partial and multiple transversals Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino ----------------------------------------------------------------= ---- 10:00 - 10:50 SESSION 2 Revisiting the correspondence between cut elimination and normalisation Jos=E9 Espirito Santo Negation Elimination from Simple Equational Formulae Reinhard Pichler ----------------------------------------------------------------= ---- (Coffee Break 10:50 - 11:10) ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 1 Hardness of set cover with intersection 1 V.S. Anil Kumar, Sunil Arya, H. Ramesh Strong inapproximability of the basic k-Spanner Problem Michael Elkin, David Peleg Approximating Minimum Spanning Sets in Hypergraphs and Polymatroids Gregor Baudis, Clemens Gr=F6pl, Stefan Hougardy, Till Nierhoff, Hans J=FCrgen Pr=F6mel ----------------------------------------------------------------= ---- 11:10 - 12:25 SESSION 2 Infinite series parallel posets: logic and languages Dietrich Kuske On deciding if deterministic Rabin language is in Buchi class Tomasz Fryderyk Urbanski On Message Sequence Graphs and Finitely Generated Regular MSC Languages Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P.S. Thiagarajan ----------------------------------------------------------------= ---- (Lunch 12:30 - 14:30) ----------------------------------------------------------------= ---- 14:30 - 15:30 INVITED TALK Pseudorandomness Oded Goldreich 15:30 - 16:20 SESSION 1 A bound on the capacity of backoff and acknowledgement based protocols Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson Deterministic radio broadcasting Bogdan Chlebus, Leszek Gasieniec, Anna =D6stlin, John Michael Robson ----------------------------------------------------------------= ---- 15:30 - 16:20 SESSION 2 A Finite w-complete Equational Specification of Interleaving Wan Fokkink, Bas Luttik A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors Mario Bravetti, Roberto Gorrieri ----------------------------------------------------------------= ---- (Coffee Break 16:20 - 16:40) ----------------------------------------------------------------= ---- 16:40 - 17:30 SESSION 1 Tight size bounds for packet headers in narrow meshes Micah Adler, Faith Fich, Leslie Ann Goldberg, Mike Paterson Wavelength assignment problem on all-optical networks with k fibres per link Luciano Margara, Janos Simon ----------------------------------------------------------------= ---- 16:40 - 17:30 SESSION 2 On the logical characterisation of performability properties Christel Baier, Boudewijn Haverkort, Holger Hermanns, Joost-Pieter Katoen On the Representation of Timed Polyhedra Olivier Bournez, Oded Maler ----------------------------------------------------------------= ---- (Conference dinner 20:00) ----------------------------------------------------------------= ---- -------------------------------------------------------------------= ----- Friday July 14th 9:00 - 10:00 INVITED TALK Min-wise Independent Permutations: Theory and Practice Andrei Broder 10:00 - 10:50 SESSION 1 Testing acyclicity of directed graphs in sublinear time Michael Bender, Dana Ron Computing the girth of a planar graph Hristo N. Djidjev -------------------------------------------------------------------= ----- 10:00 - 10:50 SESSION 2 Lower bounds are not easier over the reals: inside PH Herv=E9 Fournier, Pascal Koiran Unlearning helps Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan -------------------------------------------------------------------= ----- (Coffee Break 10:50 - 11:10) -------------------------------------------------------------------= ----- 11:10 - 12:25 SESSION 1 Fast approximation schemes for Euclidean multiconnectivity problems Artur Czumaj, Andrzej Lingas Approximate TSP in graphs with forbidden minors Michelangelo Grigni Polynomial time approximation schemes for general multiprocessor job shop scheduling Klaus Jansen and Lorant Porkolab -------------------------------------------------------------------= ----- 11:10 - 12:25 SESSION 2 The many faces of a translation Pierre McKenzie, Thomas Schwentick, Denis Th=E9rien, Heribert Vollmer Gales and the constructive dimension of individual sequences Jack Lutz The global power of additional queries to p-random oracles Wolfgang Merkle -------------------------------------------------------------------= ----- (Lunch 12:30 - 14:30) -------------------------------------------------------------------= ----- WORKSHOPS START AT 14:30 (* See individual workshop programs for schedule details.) -------------------------------------------------------------------= ----- Registration You may register electronically (opens in the begining of april) at t= he ICALP home page. The online registration application accepts MasterCa= rd, Visa and American Express cards. If you do not have one of these cred= it cards, or if you prefer not to register online, please download the registration form. Registration Fees Includes entrance to all sessions and workshops, a copy of the procee= dings, a copy of the workshops proceedings, luncheon, coffee breaks, social = events and the EATCS membership for one year. (1US=3D1.67CHF at the moment o= f the print) CHF 550.00 EATCS members registration received before June 1, 2000 CHF 650.00 Non EATCS members registration received before June 1, 2= 000 CHF 400.00 Student registration received before June 1, 2000 CHF 650.00 EATCS members registration after June 1, 2000 CHF 750.00 Non EATCS members registration after June 1, 2000 CHF 500.00 Student registration after June 1, 2000 CHF 150.00 Workshops only registration received before June 1, 2000 CHF 200.00 Workshops only registration after June 1, 2000 Practical Information -------------------------------------------------------------------= ----- -------------------------------------------------------------------= ----- Conference Site Universit=E9 de Gen=E8ve - UNI BASTIONS 3, place de l'Universit=E9 (at Rue de Candolle) Geneva How to get to Geneva Swissair and Crossair have been appointed official carrier for ICALP = '2000. To book the special conference fare, please contact your nearest Swis= sair office or, in the US and UK, the appointed travel agent listed below.= To obtain a discount fare, give the ticket agent the code SR IDS page GC= GRF C00-C26 and refer to the event as the 27th International Colloquium o= n Automata, Languages and Programming. The official Swissair designated airline ticketing agency is North American Participants: Conferences International, Inc. Toll Free in US and Canada 1-800-221-8747 Fax: 1-508-872-5566 United Kingdom Participants: Karen Hammond Tel 44-171-499-7611 Fax 44-171-493-0326 Participants from other countries should contact their nearest Swissa= ir office. If other arrangements including ground and rail are required, contact your travel agent for assistance. Accommodations In 2000, ICALP will be held in the old campus of the University of Ge= neva. The hotels listed below have reserved a block of rooms at special ICA= LP rates. The discounted rates offered by the Hotel du Midi, a very pres= tigious 4 star establishment, are an especially good value. Prices for the hotels are guaranteed but due to the high demand of ro= oms during the month of July in Geneva, register as early as possible to = assure your choice. The hotels are within 5-15 minutes walking distance from= the University of Geneva campus. To reserve accommodations, contact the selected hotel, preferably, by= fax and furnish the following information: Name - Affiliation - Address Phone and Fax Accommodations requested (Single/Double) Number in party (Ages of children) Arrival and Departure Date/Time Credit Card Guarantee (Most are accepted) Please cite: Special rate for the University of Geneva - ICALP 20= 00 NOGA HILTON GENEVE ***** CONTACT Mme Valerie Bonvin TEL +41 22 908-9193 FAX +41 22 908-9091 SINGLE CHF 330 DOUBLE CHF 380 HOTEL DU MIDI **** CONTACT Mme S. Ianna TEL +41 22 731-7800 FAX +41 22 731-0020 SINGLE CHF 140 DOUBLE CHF 180 HOTEL LE GRENIL *** CONTACT Mme Christine Hager TEL +41 22 328-3055 FAX +41 22 321-6010 SINGLE CHF 95 (breakfast included) DOUBLE CHF 130 (breakfast included) Other Accommodations For information and reservation of other accommodations and tour pack= ages, you or your travel agent may contact the Geneva Tourist Office. You c= an fax your data as above, any other relevant information and ask for a room reservation. Fax +41 22 909-7021 or call +41 22 909-7020 or write PO = Box 1602, CH-1211 Geneva 1, Switzerland. Also, take a look at their site = at http://www.geneve-tourisme.ch Alternatively, a limited number of very inexpensive rooms are availab= le at the Student Housing (Cit=E9 Universitaire). If you are interested in = such accomodations please contact icalp@cui.unige.ch Local Transportation 30. Alternatively you may take the train from the airport to the main= train station - a 5 minute walk from the first two hotels. The ride will co= st around CHF 5 and will take 10 minutes. Purchase a ticket before board= ing the train. the enclosed map. The University is located at the park called Promen= ade des Bastions. By public transportation, take tramway number 13 from the main train = station to the fourth stop (called Plainpalais). From there walk by rue du Co= nseil G=E8n=E8ral until you reach the Promenade des Bastions. Note: When using any local transportation, you need to purchase a tic= ket in advance at the machine located at the bus stop; the cost is CHF 2.20.= This ticket is valid for one hour and you may take as many connections as = you want. Also note that the machine does not give change, and if you ent= er a bus without a valid transportation ticket you risk being required to = pay a fine of about CHF 100 and a visit to the police station. Cuisine At ICALP '2000, luncheon will be served on the University campus to a= ll registrants on all five days and refreshments will be available durin= g breaks. On Thursday evening, there will be the official banquet of th= e conference. Please be sure to indicate on your registration form whet= her you prefer vegetarian meals. At other times, participants will have a broad choice of dining optio= ns offering international and gourmet fare all within walking distance o= f accommodations and many along the shores of Lake Geneva. The traditio= nal and most popular dishes among the local population are cheese fondue and raclette, delicious local wines, and lake perch. Currency and Credit Cards The unit of currency is the Swiss franc (CHF). Notes are issued in denominations of 10, 20, 50, 100, 200, and 1,000. Coins are issued in denominations of 5, 10, and 20 centimes, and .5, 1, 2, and 5 Swiss fr= ancs. At the moment of the print, 1US was worth CHF 1.67, but since this ra= te changes very often, check the real rate at the necessary moment. Most hotels, large stores, restaurants, and petrol stations accept all maj= or credit cards (American Express, MasterCard, Visa, Diners Club, Euroca= rd). Location Geneva is situated along the banks of Lac L=E9man (Lake Geneva) and L= e Rh=F4ne. The lake showcases the plumed fountain Jet d'Eau, and various distric= ts of Geneva are connected by bridges across the waterways. The University = of Geneva where ICALP '2000 will convene is located on the `Left Bank' o= ff Place Neuve and along the Promenade des Bastions near the Old Town se= ction of Geneva. The two first ICALP designated hotels (Noga and du Midi) are located lakeside - on the `Right Bank' - and are within walking distance of t= he University campus. It is a 10-15 minute walk which crosses through `O= ld Town'. Also, there is regular bus service running to the University, = so ICALP participants may come and go throughout the day. The Hotel Le G= renil and the University are both situated on the `Left Bank' and are very = close. Geneva is a city of water parks and gardens and welcoming walkways wh= ich encourage exploration of the historical sites, museums, and internati= onal business and shopping districts. The University of Geneva is located = near `Old Town' an area dotted with sidewalk cafes, student life, and buil= ding antiquities dating back to the 5th century. Geneva is a crossroads situated in the heart of Europe and linked to = the world by a vast network of motorways, airlines and railways. For thos= e planning to attend ICALP'2000 in Geneva, it is an excellent opportuni= ty to organize short trips into the countryside of charming villages and vineyards. Tours to please all ages and interests are available inclu= ding afternoon train excursions, shopping cruises on Lake Geneva and The R= hone, and bus and cablecar trips in the Alps. For some, the most inviting attraction will be mountain climbing. The= high mountains are situated less than half an hour drive from Geneva. In e= arly July, a very popular and almost mandatory activity is swimming in the= lake Geneva, so serious and not so serious swimmers should plan accordingl= y! Climate The climate in early July should be warm but still very pleasant with= nice evenings and breezes off the Lake. There may be showers but we can al= so expect sunny days. Passports and Visas A valid passport is required for entry into Switzerland. Some nationa= ls may also require a visa for Switzerland, and if you plan to visit France = one may be required there. Please check with your travel agent or consulate t= o determine whether a visa will be required.