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

Accepted Papers


A 17/8 approximation algorithm for rectangle tiling
Katarzyna Paluch
A 2O(n1-1/d) time algorithm for d-dimensional protein folding in the HP-model
Bin Fu and Wei Wang
A faster algorithm for Minimum Cycle Basis of graphs
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
A General Technique for Managing Strings in Comparison-Driven Data Structures
Gianni Franceschini, Roberto Grossi
A new algorithm for optimal constraint satisfaction and its implications
Ryan Williams
A polynomial quantum query lower bound for the set equality problem
Gatis Midrijanis
A PTAS for Embedding Hypergraph in a Cycle
Xiaotie Deng, Guojun Li
A Time Lower Bound for Satisfiability
Dieter van Melkebeek and Ran Raz
Algorithms for Multi-Product Pricing
Gagan Aggarwal and Tomas Feder and Rajeev Motwani and An Zhu
Almost optimal decentralized routing in long-range contact networks
Emmanuelle Lebhar and Nicolas Schabanel
An Analog Characterization of Computable Functions Over the Real Numbers
O. Bournez and E. Hainry
Approximating Longest Directed Paths and Cycles
Andreas Björklund, Thore Husfeldt, Sanjeev Khanna
Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and its Variants in Network Design
Raja Jothi, Balaji Raghavachari
Bounded fixed-parameter tractability and log2 n nondeterministic bits
Joerg Flum, Martin Grohe, and Mark Weyer
Closest Pair Problems in Very High Dimensions
Piotr Indyk, Moshe Lewenstein, Ohad Lipsky and Ely Porat
Coloring semirandom graphs optimally
Amin Coja-Oghlan
Communication vs. Computation
Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim and S Venkatesh
Competition Induced Preferential Attachment
Noam Berger, Christian Borgs, Jennifer Chayes, Raissa D`Souza, Robert Kleinberg
Complexity of Pseudoknot Prediction in Simple Models
Rune Bang Lyngsø
Computing quickly succinct trade-off curves
Sergei Vassilvitskii, Mihalis Yannakakis
Coordination mechanisms
George Christodoulou, Elias Koutsoupias, Akash Nanavati
Definitions and Bounds for Self-healing Key Distribution Schemes
Carlo Blundo, Paolo D`Arco, and Alfredo De Santis
Deterministic M2M Multicast in Radio Networks
Leszek Gasieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin
Dynamic Price Sequence and Incentive Compatibility
Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew C Yao
Easily refutable subformulas of large random 3CNF formulas
Uriel Feige and Eran Ofek
Ecological Turing machines
Durand, Muchnik, Ushakov and Vereshchagin
Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities
Bruno Codenotti and Kasturi Varadarajan
Efficient Consistency Proofs on a Committed Database
Charles Rackoff, Rafail Ostrovsky, Adam Smith
Exact (exponential) algorithms for treewidth and minimum fill-in
Fedor Fomin, Dieter Kratsch, Ioan Todinca
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Michael Alekhnovich, Edward A. Hirsch. Dmitry Itsykson
External memory algorithms for diameter and all-pair shortest-paths on sparse graphs
Lars Arge, Ulrich Meyer, Laura Toma
Fairness to All While Downsizing
Bala Kalyanasundaram & Mahendran Velauthapillai
Fast parameterized algorithms for graphs on surfaces
Fedor Fomin, Dimitrios Thilikos
Further Improvements in Competitive Guarantees for QoS Buffering
M. Mahdian, N. Bansal, L. Fleischer, T. Kimbrel, B. Schieber, M. Sviridenko
Group Spreading: A Protocol for Provably Secure Distributed Name Service
Baruch Awerbuch and Christian Scheideler
Hard-core Measures for Uniform Mildly Hard Problems
Thomas Holenstein
Hardness of string similarity search and other indexing problems
S. Cenk Sahinalp, Andrey Utis
Improved Results for Data Migration and Open Shop Scheduling
Rajiv Gandhi and Magnus M. Halldorsson and Guy Kortsarz and Hadas Shachnai
LA and the Hajos Calculus
Michael Soltys
Learning a Hidden Subgraph
Noga Alon and Vera Asodi
Linear Taxes Suffice
Lisa Fleischer
Linear time list decoding in error-free settings
Venkatesan Guruswami and Piotr Indyk
Locally consistent constraint satisfaction problems
Zdenek Dvorak, Daniel Kral, Ondrej Pangrac
Monotonicity Testing over Graph Products
Shirley Halevy and Eyal Kushilevitz
Nash Equilibria in Discrete Routing Games with Convex Latency Functions
Martin Gairing, Thomas Luecking, Marios Mavronicolas, Burkhard Monien, Manuel Rode
On Graph Problems in a Semi-Streaming Model
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang
On the power of Ambainis`s lower bounds
Shengyu Zhang
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help
Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomas Tichy
Online Scheduling with Bounded Migration
Peter Sanders, Naveen Sivadasan, Martin Skutella
Optimal Website Design with the Constrained Subtree Selection Problem
Brent Heeringa and Micah Adler
Property testing of regular tree languages
Frederic Magniez and Michel de Rougemont
Propositional PSPACE Reasoning with Boolean Programs vs. Quantified Boolean Formulas
Alan Skelley
Quantum query complexity of some graph problems
Christoph Dürr, Mark Heiligman, Peter Høyer, Mehdi Mhalla
Regular solutions of language inequalities and well quasi-orders
Michal Kunc
Selfish Unsplittable Flows
Dimitris Fotakis, Spyros Kontogiannis, Paul Spirakis
Simple Permutations Mix Well
Shlomo Hoory, Avner Magen, Steve Myers and Charles Rackoff
Solving Two-Variable Word Equations
Robert Dabrowski, Wojciech Plandowski
Some results on effective randomness
Wolfgang Merkle, Nenad Mihailovic, and Theodore A. Slaman
Sublinear-Time Approximation for Clustering via Random Sampling
Artur Czumaj and Christian Sohler
Succinct representation of Functions
J. Ian Munro and S. Srinivasa Rao
The complexity of partition functions
Andrei Bulatov and Martin Grohe
The black-box complexity of nearest-neighbor search
Robert Krauthgamer and James R. Lee
The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs
S. Nikoletseas, C. Raptopoulos and P. Spirakis
The Minimum-Entropy Set Cover Problem
Eran Halperin and Richard M. Karp
The Power of Verification for One-Parameter Agents
V. Auletta and R. De Prisco and P. Penna and P. Persiano
Transparent long proofs: A first PCP theorem for NPR
Klaus Meer
Universality in Quantum Computation
Emmanuel Jeandel
Wavelength Assignment in Optical Networks with Fixed Fiber Capacity
Matthew Andrews and Lisa Zhang
Word problems on compressed words
Markus Lohrey


A Calculus of Coroutines
J. Laird
A Calibration of Ineffective Theorems of Analysis in a Hierarchy of Semi-Classical Logical Principles
Michael Toftdal
A Categorical Model for the Geometry of Interaction
Esfandiar Haghverdi and Philip Scott
A Generalisation of Pre-Logical Predicates to Simply Typed Formal Systems
Shin-ya Katsumata
A lambda-Calculus for Resource Separation
Robert Atkey
A Note on Karr´s Algorithm
Markus Müller-Olm, Helmut Seidl
A Syntactic Characterization of Distributive LTL Queries
Marko Samer, Helmut Veith
Backtracking games and inflationary fixed points
Anuj Dawar, Erich Grädel, Stephan Kreutzer
Comparing recursion, replication, and iteration in process calculi
N.Busi, M.Gabbrielli, G.Zavattaro
Counting in Trees for Free
Helmut Seidl, Thomas Schwentick, Anca Muscholl, Peter Habermehl
Deciding knowledge in security protocols under equational theories
Martin Abadi and Veronique Cortier
Entropy as a fixed point
Keye Martin
Extensional Theories and Rewriting
Grigore Rosu
Games With Winning Conditions of High Borel Complexity
Olivier SERRE
Greedy Regular Expression Matching
Alain Frisch and Luca Cardelli
Initial Value Problems in Domain Theory
Abbas Edalat and Dirk Pattinson
Interactive Observability in Ludics
Claudia Faggian
Linear and Branching Metrics for Quantitative Transition Systems
Luca de Alfaro, Marco Faella, and Marielle Stoelinga
Model Checking with Multi-Valued Logics
Glenn Bruns and Patrice Godefroid
On Randomization versus Synchronization in Distributed Systems
Hagen Völzer
On the Expressive Power of Monadic Least Fixed Point Logic
Nicole Schweikardt
Optimal Reachability for Weighted Timed Games
Rajeev Alur, Mikhail Bernadskiy, P. Madhusudan
Projecting games on hypercoherences
Pierre Boudes
Representing Nested Inductive Types using W-types
Michael Abbott, Thorsten Altenkirch, Neil Ghani
Syntactic Control of Concurrency
D. Ghica, A. Murawski, L. Ong
The Complexity of Equivariant Unification
James Cheney
Towards an algebraic theory of typed mobile processes
Yuxin Deng and Davide Sangiorgi
Tree-Walking Automata Cannot Be Determinized
Mikolaj Bojanczyk and Thomas Colcombet

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