31st International Colloquium on

Automata, Languages and Programming

ICALP'04 - LICS'04
ICALP schedule
Call for Papers
Accepted Papers
Travelling to Turku
Program committee
Invited speakers
Organizing committee
Previous conferences
Gödel Prize
July 12-16, 2004, Turku, Finland

ICALP Schedule

LICS schedule
Workshop schedules

18:00 Registration and get-together (in Mauno Koivisto Center)

8:30 Registration (in Mauno Koivisto Center)
9:00 Opening Vice rector Harri Lönnberg
9:15 Invited talk: Theory and Practice of Probabilistic Counting
Philippe Flajolet, Chair: Juhani Karhumäki
  Session A 1
Chair: Philippe Flajolet
Session A 2
Chair: Julien Cassaigne
10:15 Learning a Hidden Subgraph
Noga Alon and Vera Asodi
Ecological Turing machines
Durand, Muchnik, Ushakov, and Vereshchagin
10:45 Coffee break
11:15 A new algorithm for optimal constraint satisfaction and its implications
Ryan Williams
Regular solutions of language inequalities and well quasi-orders
Michal Kunc
11:45 The Minimum-Entropy Set Cover Problem
Eran Halperin and Richard M. Karp
Word problems on compressed words
Markus Lohrey
12:15 A 2O(n1-1/d) time algorithm for d-dimensional protein folding in the HP-model
Bin Fu and Wei Wang
Solving Two-Variable Word Equations
Robert Dabrowski and Wojciech Plandowski
12:45 Lunch
14:00 Invited talk: Grammar Compression, LZ-encodings and String Algorithms with Implicit Input
Wojciech Rytter, Chair: Grzegorz Rozenberg
  Session A 3
Chair: Volker Diekert
Session A 4
Chair: Mika Hirvensalo
15:00 Monotonicity Testing over Graph Products
Shirley Halevy and Eyal Kushilevitz
An Analog Characterization of Computable Functions Over the Real Numbers
O. Bournez and E. Hainry
15:30 Property testing of regular tree languages
Frederic Magniez and Michel de Rougemont
Transparent long proofs: A first PCP theorem for NPR
Klaus Meer
16:00 Coffee break
16:30 Coloring semirandom graphs optimally
Amin Coja-Oghlan
Efficient Consistency Proofs on a Committed Database
Charles Rackoff, Rafail Ostrovsky, and Adam Smith
17:00 Competition Induced Preferential Attachment
Noam Berger, Christian Borgs, Jennifer Chayes, Raissa D`Souza, and Robert Kleinberg
Hardness of string similarity search and other indexing problems
S. Cenk Sahinalp and Andrey Utis
17:30 The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs
S. Nikoletseas, C. Raptopoulos, and P. Spirakis
Some results on effective randomness
Wolfgang Merkle, Nenad Mihailovic, and Theodore A. Slaman
18:00 End
19:30 Reception at the VPK Banquet House

9:00 Invited talk: The Past, Present, and Future of Web Search Engines
Monika Henzinger, Chair: Jan van Leeuwen
  Session A 5
Chair: Wilfried Brauer
Session B 1
Chair: Wolfgang Thomas
10:00 Computing quickly succinct trade-off curves
Sergei Vassilvitskii and Mihalis Yannakakis
Deciding knowledge in security protocols under equational theories
Martin Abadi and Veronique Cortier
10:30 Coffee break
11:00 Algorithms for Multi-Product Pricing
Gagan Aggarwal, Tomas Feder, Rajeev Motwani, and An Zhu
On the Expressive Power of Monadic Least Fixed Point Logic
Nicole Schweikardt
11:30 Further Improvements in Competitive Guarantees for QoS Buffering
M. Mahdian, N. Bansal, L. Fleischer, T. Kimbrel, B. Schieber, and M. Sviridenko
Counting in Trees for Free
Helmut Seidl, Thomas Schwentick, Anca Muscholl, and Peter Habermehl
12:00 Optimal Website Design with the Constrained Subtree Selection Problem
Brent Heeringa and Micah Adler
Tree-Walking Automata Cannot Be Determinized
Mikolaj Bojanczyk and Thomas Colcombet
12:30 Lunch
  Session A 6
Chair: Burkhard Monien
Session B 2
Chair: Igor Walukiewicz
14:00 Almost optimal decentralized routing in long-range contact networks
Emmanuelle Lebhar and Nicolas Schabanel
Representing Nested Inductive Types using W-types
Michael Abbott, Thorsten Altenkirch, and Neil Ghani
14:30 Definitions and Bounds for Self-healing Key Distribution Schemes
Carlo Blundo, Paolo D`Arco, and Alfredo De Santis
A Calculus of Coroutines
J. Laird
15:00 Deterministic M2M Multicast in Radio Network
Leszek Gasieniec, Evangelos Kranakis, Andrzej Pelc, and Qin Xin
A Generalisation of Pre-Logical Predicates to Simply Typed Formal Systems
Shin-ya Katsumata
15:30 Fairness to All While Downsizing
Bala Kalyanasundaram and Mahendran Velauthapillai
Extensional Theories and Rewriting
Grigore Rosu
16:00 Coffee break
  Session A 7
Chair: Juraj Hromkovic
Session B 3
Chair: Robert Harper
16:30 Wavelength Assignment in Optical Networks with Fixed Fiber Capacity
Matthew Andrews and Lisa Zhang
Projecting games on hypercoherences
Pierre Boudes
17:00 Group Spreading: A Protocol for Provably Secure Distributed Name Service
Baruch Awerbuch and Christian Scheideler
A Categorical Model for the Geometry of Interaction
Esfandiar Haghverdi and Philip Scott
17:30 Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and its Variants in Network Design
Raja Jothi and Balaji Raghavachari
Interactive Observability in Ludics
Claudia Faggian
18:00 End
18:15 Springer Reception in honour of 20 years of "EATCS Monographs and Texts Series"
19:00 EATCS General Assembly

9:00 Invited talk: Testing, Optimization, and Games
Mihalis Yannakakis, Chair: Josep Diaz
  Session A 8
Chair: Alexander Razborov
Session B 4
Chair: Jean-Pierre Jouannaud
10:00 Quantum query complexity of some graph problems
Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla
A Calibration of Ineffective Theorems of Analysis in a Hierarchy of Semi-Classical Logical Principles
Michael Toftdal
10:30 Coffee break
11:00 A polynomial quantum query lower bound for the set equality problem
Gatis Midrijanis
On Randomization versus Synchronization in Distributed Systems
Hagen Völzer
11:30 On the power of Ambainis`s lower bounds
Shengyu Zhang
Comparing recursion, replication, and iteration in process calculi
N.Busi, M.Gabbrielli, and G.Zavattaro
12:00 Universality in Quantum Computation
Emmanuel Jeandel
Towards an algebraic theory of typed mobile processes
Yuxin Deng and Davide Sangiorgi
12:30 Lunch
13:45 Gödel Prize and Gödel Lecture
14:45 EATCS Award and Award Acceptance Speech
15:25 ICALP and LICS awards
15:45 Andrei Voronkov: Scientific Contribution of Harald Ganzinger
16:00 Coffee break
17:30 Excursion

9:00 Invited talk: Feasible Proofs and Computations: Partnership and Fusion
Alexander Razborov, Chair: Mogens Nielsen
  Session A 9
Chair: Wojciech Rytter
Session A 10
Chair: Giuseppe Italiano
Session B 5
Chair: Mariangiola Dezani
10:00 A faster algorithm for Minimum Cycle Basis of graphs
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna Paluch
Simple Permutations Mix Well
Shlomo Hoory, Avner Magen, Steve Myers, and Charles Rackoff
Entropy as a fixed point
Keye Martin
10:30 Coffee break
11:00 Improved Results for Data Migration and Open Shop Scheduling
Rajiv Gandhi, Magnus M. Halldorsson, Guy Kortsarz, and Hadas Shachnai
Sublinear-Time Approximation for Clustering via Random Sampling
Artur Czumaj and Christian Sohler
A Syntactic Characterization of Distributive LTL Queries
Marko Samer and Helmut Veith
11:30 Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help
Marek Chrobak, Wojciech Jawor, Jiri Sgall, and Tomas Tichy
Closest Pair Problems in Very High Dimensions
Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, and Ely Porat
Model Checking with Multi-Valued Logics
Glenn Bruns and Patrice Godefroid
12:00 Online Scheduling with Bounded Migration
Peter Sanders, Naveen Sivadasan, and Martin Skutella
The black-box complexity of nearest-neighbor search
Robert Krauthgamer and James R. Lee
Linear and Branching Metrics for Quantitative Transition Systems
Luca de Alfaro, Marco Faella, and Marielle Stoelinga
12:30 Lunch
14:00 Invited talk: What do program logics and type systems have in common?
Martin Hofmann , Chair: Donald Sannella
  Session A 11
Chair: Pavlos Spirakis
Session A 12
Chair: Albert Atserias
Session B 6
Chair: Leszek Pacholski
15:00 Approximating Longest Directed Paths and Cycles
Andreas Björklund, Thore Husfeldt, and Sanjeev Khanna
A General Technique for Managing Strings in Comparison-Driven Data Structures
Gianni Franceschini and Roberto Grossi
A lambda-Calculus for Resource Separation
Robert Atkey
15:30 A PTAS for Embedding Hypergraph in a Cycle
Xiaotie Deng and Guojun Li
Succinct representation of Functions
J. Ian Munro and S. Srinivasa Rao
Syntactic Control of Concurrency
D. Ghica, A. Murawski, and L. Ong
16:00 Coffee break
16:30 A 17/8 approximation algorithm for rectangle tiling
Katarzyna Paluch
Communication vs. Computation
Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, and S Venkatesh
A Note on Karr's Algorithm
Markus Müller-Olm and Helmut Seidl
17:00 On Graph Problems in a Semi-Streaming Model
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang
Linear time list decoding in error-free settings
Venkatesan Guruswami and Piotr Indyk
The Complexity of Equivariant Unification
James Cheney
17:30 External memory algorithms for diameter and all-pair shortest-paths on sparse graphs
Lars Arge, Ulrich Meyer, and Laura Toma

Greedy Regular Expression Matching
Alain Frisch and Luca Cardelli
18:00 End
19:30 Congress Dinner

9:00 Invited talk: Self-Adjusting Computation
Robert Harper, Chair: Martin Hofmann
  Session A 13
Chair: Jiri Wiedermann
Session B 7
Chair: Anca Muscholl
10:00 Complexity of Pseudoknot Prediction in Simple Models
Rune Bang Lyngsø
Initial Value Problems in Domain Theory
Abbas Edalat and Dirk Pattinson
10:30 Coffee break
11:00 Exact (exponential) algorithms for treewidth and minimum fill-in
Fedor Fomin, Dieter Kratsch, and Ioan Todinca
Backtracking games and inflationary fixed points
Anuj Dawar, Erich Grädel, and Stephan Kreutzer
11:30 Bounded fixed-parameter tractability and log2  n nondeterministic bits.
Joerg Flum, Martin Grohe, and Mark Weyer
Games With Winning Conditions of High Borel Complexity
Olivier Serre
12:00 Fast parameterized algorithms for graphs on surfaces
Fedor Fomin and Dimitrios Thilikos
Optimal Reachability for Weighted Timed Games
Rajeev Alur, Mikhail Bernadskiy, and P. Madhusudan
12:30 Lunch
  Session A 14
Chair: Jarkko Kari
Session A 15
Chair: Tero Harju
14:00 The Power of Verification for One-Parameter Agents
V. Auletta, R. De Prisco, P. Penna, and P. Persiano
The complexity of partition functions
Andrei Bulatov and Martin Grohe
14:30 Linear Taxes Suffice
Lisa Fleischer
Locally consistent constraint satisfaction problems
Zdenek Dvorak, Daniel Kral, and Ondrej Pangrac
15:00 Dynamic Price Sequence and Incentive Compatibility
Ning Chen, Xiaotie Deng, Xiaoming Sun, and Andrew C Yao
A Time Lower Bound for Satisfiability
Dieter van Melkebeek and Ran Raz
15:30 Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities
Bruno Codenotti and Kasturi Varadarajan
Easily refutable subformulas of large random 3CNF formulas
Uriel Feige and Eran Ofek
16:00 Coffee break
  Session A 16
Chair: Keijo Ruohonen
Session A 17
Chair: Magnus Steinby
16:30 Selfish Unsplittable Flows
Dimitris Fotakis, Spyros Kontogiannis, and Paul Spirakis
LA and the Hajos Calculus
Michael Soltys
17:00 Coordination mechanisms
George Christodoulou, Elias Koutsoupias, and Akash Nanavati
Propositional PSPACE Reasoning with Boolean Programs vs. Quantified Boolean Formulas
Alan Skelley
17:30 Nash Equilibria in Discrete Routing Games with Convex Latency Functions
Martin Gairing, Thomas Luecking, Marios Mavronicolas, Burkhard Monien, and Manuel Rode
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Michael Alekhnovich, Edward A. Hirsch, and Dmitry Itsykson
18:00 End

Historical Turku

Ukko-Pekka Cruise

Petri Salmela
Last modified: Tue Jul 20 10:24:32 EEST 2004