|
|
|
July 12-16, 2004, Turku, Finland
|
|
ICALP Schedule
LICS schedule
Workshop schedules
Sunday
| 18:00 |
Registration and get-together (in Mauno Koivisto Center) |
Monday
| 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
|
Tuesday
| 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
|
Wednesday
| 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
|
Thursday
| 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
|
Friday
| 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
|
|
