[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