[mercury-users] icalp2000-program and registration

POWELL Olivier Olivier.Powell at cui.unige.ch
Fri Mar 31 20:58:24 AEST 2000


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üttgen, 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äki, 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öning

               Closest Vectors, Successive Minima and Dual
               HKZ-Bases of Lattices
               Johannes Blömer



     --------------------------------------------------------------------

          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ános Csirik, Gerhard Woeginger

               Optimal projective algorithms for the list
               update problem
               Christoph Ambühl, Bernd Gärtner, 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ée

               Planar maps and Airy phenomena
               Cyril Banderier, Philippe Flajolet, Gilles
               Schaeffer, Michèle Soria



     --------------------------------------------------------------------

          15:30  - 16:20

          SESSION 2


               Analysing Input Output Capabilities of Mobile
               Processes with a Generic Type System
               Barbara König

               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üller

               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äki, Ion Petre

               On the power of tree-walking automata
               Frank Neven, Thomas Schwentick

               Determinization of transducers over infinite
               words
               Marie-Pierre Béal, 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é 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öpl, Stefan Hougardy,
               Till Nierhoff, Hans Jürgen Prömel


     --------------------------------------------------------------------

          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 Östlin,
               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é 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érien,
          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 the
ICALP home page. The online registration application accepts MasterCard,
Visa and American Express cards. If you do not have one of these credit
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 proceedings,
a copy of the workshops proceedings, luncheon, coffee breaks, social events
and the EATCS membership for one year. (1US=1.67CHF at the moment of the
print)

CHF 550.00   EATCS members registration received before June 1, 2000

CHF 650.00   Non EATCS members registration received before June 1, 2000

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é de Genève - UNI BASTIONS
                3, place de l'Université (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 Swissair
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 GCGRF
C00-C26 and refer to the event as the 27th International Colloquium on
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 Swissair
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 Geneva.
The hotels listed below have reserved a block of rooms at special ICALP
rates. The discounted rates offered by the Hotel du Midi, a very prestigious
4 star establishment, are an especially good value.

Prices for the hotels are guaranteed but due to the high demand of rooms
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 2000

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 packages,
you or your travel agent may contact the Geneva Tourist Office. You can 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 available at
the Student Housing (Cité Universitaire). If you are interested in such
accomodations please contact icalp at cui.unige.ch


                            Local Transportation

>From the airport:
A taxi from the airport to either hotels or University will cost about CHF
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 cost
around CHF 5 and will take 10 minutes. Purchase a ticket before boarding the
train.

>From hotels to the University:
It is a 10 minute walk from the first two hotels. You may cross the river
via either the Pont des Bergues or Pont de la Machine and then take Rue de
la Corraterie to Place Neuve. From the other hotel is a very short walk, see
the enclosed map. The University is located at the park called Promenade 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 Conseil
Gènèral until you reach the Promenade des Bastions.

Note: When using any local transportation, you need to purchase a ticket 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 enter 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 all
registrants on all five days and refreshments will be available during
breaks. On Thursday evening, there will be the official banquet of the
conference. Please be sure to indicate on your registration form whether you
prefer vegetarian meals.

At other times, participants will have a broad choice of dining options
offering international and gourmet fare all within walking distance of
accommodations and many along the shores of Lake Geneva. The traditional 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 francs.
At the moment of the print, 1US was worth CHF 1.67, but since this rate
changes very often, check the real rate at the necessary moment. Most
hotels, large stores, restaurants, and petrol stations accept all major
credit cards (American Express, MasterCard, Visa, Diners Club, Eurocard).


                                  Location

Geneva is situated along the banks of Lac Léman (Lake Geneva) and Le Rhône.
The lake showcases the plumed fountain Jet d'Eau, and various districts of
Geneva are connected by bridges across the waterways. The University of
Geneva where ICALP '2000 will convene is located on the `Left Bank' off
Place Neuve and along the Promenade des Bastions near the Old Town section
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 the
University campus. It is a 10-15 minute walk which crosses through `Old
Town'. Also, there is regular bus service running to the University, so
ICALP participants may come and go throughout the day. The Hotel Le Grenil
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 which
encourage exploration of the historical sites, museums, and international
business and shopping districts. The University of Geneva is located near
`Old Town' an area dotted with sidewalk cafes, student life, and building
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 those
planning to attend ICALP'2000 in Geneva, it is an excellent opportunity to
organize short trips into the countryside of charming villages and
vineyards. Tours to please all ages and interests are available including
afternoon train excursions, shopping cruises on Lake Geneva and The Rhone,
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 early
July, a very popular and almost mandatory activity is swimming in the lake
Geneva, so serious and not so serious swimmers should plan accordingly!


                                  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 also
expect sunny days.


                            Passports and Visas

A valid passport is required for entry into Switzerland. Some nationals 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 to
determine whether a visa will be required.




More information about the users mailing list