31. ICALP 2004:
Turku,
Finland
Josep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella (Eds.):
Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings.
Lecture Notes in Computer Science 3142 Springer 2004, ISBN 3-540-22849-7 BibTeX
Invited Talks
Contributed Papers
- Martín Abadi, Véronique Cortier:
Deciding Knowledge in Security Protocols Under Equational Theories.
46-58
Electronic Edition (link) BibTeX
- Michael Abbott, Thorsten Altenkirch, Neil Ghani:
Representing Nested Inductive Types Using W-Types.
59-71
Electronic Edition (link) BibTeX
- Gagan Aggarwal, Tomás Feder, Rajeev Motwani, An Zhu:
Algorithms for Multi-product Pricing.
72-83
Electronic Edition (link) BibTeX
- Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson:
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas.
84-96
Electronic Edition (link) BibTeX
- Luca de Alfaro, Marco Faella, Mariëlle Stoelinga:
Linear and Branching Metrics for Quantitative Transition Systems.
97-109
Electronic Edition (link) BibTeX
- Noga Alon, Vera Asodi:
Learning a Hidden Subgraph.
110-121
Electronic Edition (link) BibTeX
- Rajeev Alur, Mikhail Bernadsky, P. Madhusudan:
Optimal Reachability for Weighted Timed Games.
122-133
Electronic Edition (link) BibTeX
- Matthew Andrews, Lisa Zhang:
Wavelength Assignment in Optical Networks with Fixed Fiber Capacity.
134-145
Electronic Edition (link) BibTeX
- Lars Arge, Ulrich Meyer, Laura Toma:
External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs.
146-157
Electronic Edition (link) BibTeX
- Robert Atkey:
A lambda-Calculus for Resource Separation.
158-170
Electronic Edition (link) BibTeX
- Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano:
The Power of Verification for One-Parameter Agents.
171-182
Electronic Edition (link) BibTeX
- Baruch Awerbuch, Christian Scheideler:
Group Spreading: A Protocol for Provably Secure Distributed Name Service.
183-195
Electronic Edition (link) BibTeX
- Nikhil Bansal, Lisa Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko:
Further Improvements in Competitive Guarantees for QoS Buffering.
196-207
Electronic Edition (link) BibTeX
- Noam Berger, Christian Borgs, Jennifer T. Chayes, R. M. D'Souza, Robert D. Kleinberg:
Competition-Induced Preferential Attachment.
208-221
Electronic Edition (link) BibTeX
- Andreas Björklund, Thore Husfeldt, Sanjeev Khanna:
Approximating Longest Directed Paths and Cycles.
222-233
Electronic Edition (link) BibTeX
- Carlo Blundo, Paolo D'Arco, Alfredo De Santis:
Definitions and Bounds for Self-Healing Key Distribution Schemes.
234-245
Electronic Edition (link) BibTeX
- Mikolaj Bojanczyk, Thomas Colcombet:
Tree-Walking Automata Cannot Be Determinized.
246-256
Electronic Edition (link) BibTeX
- Pierre Boudes:
Projecting Games on Hypercoherences.
257-268
Electronic Edition (link) BibTeX
- Olivier Bournez, Emmanuel Hainry:
An Analog Characterization of Elementarily Computable Functions over the Real Numbers.
269-280
Electronic Edition (link) BibTeX
- Glenn Bruns, Patrice Godefroid:
Model Checking with Multi-valued Logics.
281-293
Electronic Edition (link) BibTeX
- Andrei A. Bulatov, Martin Grohe:
The Complexity of Partition Functions.
294-306
Electronic Edition (link) BibTeX
- Nadia Busi, Maurizio Gabbrielli, Gianluigi Zavattaro:
Comparing Recursion, Replication, and Iteration in Process Calculi.
307-319
Electronic Edition (link) BibTeX
- Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao:
Dynamic Price Sequence and Incentive Compatibility (Extended Abstract).
320-331
Electronic Edition (link) BibTeX
- James Cheney:
The Complexity of Equivariant Unification.
332-344
Electronic Edition (link) BibTeX
- George Christodoulou, Elias Koutsoupias, Akash Nanavati:
Coordination Mechanisms.
345-357
Electronic Edition (link) BibTeX
- Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomás Tichý:
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help.
358-370
Electronic Edition (link) BibTeX
- Bruno Codenotti, Kasturi R. Varadarajan:
Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities.
371-382
Electronic Edition (link) BibTeX
- Amin Coja-Oghlan:
Coloring Semirandom Graphs Optimally.
383-395
Electronic Edition (link) BibTeX
- Artur Czumaj, Christian Sohler:
Sublinear-Time Approximation for Clustering Via Random Sampling.
396-407
Electronic Edition (link) BibTeX
- Robert Dabrowski, Wojciech Plandowski:
Solving Two-Variable Word Equations (Extended Abstract).
408-419
Electronic Edition (link) BibTeX
- Anuj Dawar, Erich Grädel, Stephan Kreutzer:
Backtracking Games and Inflationary Fixed Points.
420-432
Electronic Edition (link) BibTeX
- Xiaotie Deng, Guojun Li:
A PTAS for Embedding Hypergraph in a Cycle (Extended Abstract).
433-444
Electronic Edition (link) BibTeX
- Yuxin Deng, Davide Sangiorgi:
Towards an Algebraic Theory of Typed Mobile Processes.
445-456
Electronic Edition (link) BibTeX
- Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin:
Ecological Turing Machines.
457-468
Electronic Edition (link) BibTeX
- Zdenek Dvorak, Daniel Král, Ondrej Pangrác:
Locally Consistent Constraint Satisfaction Problems: (Extended Abstract).
469-480
Electronic Edition (link) BibTeX
- Christoph Dürr, Mark Heiligman, Peter Høyer, Mehdi Mhalla:
Quantum Query Complexity of Some Graph Problems.
481-493
Electronic Edition (link) BibTeX
- Abbas Edalat, Dirk Pattinson:
A Domain Theoretic Account of Picard's Theorem.
494-505
Electronic Edition (link) BibTeX
- Claudia Faggian:
Interactive Observability in Ludics.
506-518
Electronic Edition (link) BibTeX
- Uriel Feige, Eran Ofek:
Easily Refutable Subformulas of Large Random 3CNF Formulas.
519-530
Electronic Edition (link) BibTeX
- Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang:
On Graph Problems in a Semi-streaming Model.
531-543
Electronic Edition (link) BibTeX
- Lisa Fleischer:
Linear Tolls Suffice: New Bounds and Algorithms for Tolls in Single Source Networks.
544-554
Electronic Edition (link) BibTeX
- Jörg Flum, Martin Grohe, Mark Weyer:
Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits.
555-567
Electronic Edition (link) BibTeX
- Fedor V. Fomin, Dieter Kratsch, Ioan Todinca:
Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In.
568-580
Electronic Edition (link) BibTeX
- Fedor V. Fomin, Dimitrios M. Thilikos:
Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up.
581-592
Electronic Edition (link) BibTeX
- Dimitris Fotakis, Spyros C. Kontogiannis, Paul G. Spirakis:
Selfish Unsplittable Flows.
593-605
Electronic Edition (link) BibTeX
- Gianni Franceschini, Roberto Grossi:
A General Technique for Managing Strings in Comparison-Driven Data Structures.
606-617
Electronic Edition (link) BibTeX
- Alain Frisch, Luca Cardelli:
Greedy Regular Expression Matching.
618-629
Electronic Edition (link) BibTeX
- Bin Fu, Wei Wang:
A 2O(n1-(1/d)log n) Time Algorithm for d-Dimensional Protein Folding in the HP-Model.
630-644
Electronic Edition (link) BibTeX
- Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien, Manuel Rode:
Nash Equilibria in Discrete Routing Games with Convex Latency Functions.
645-657
Electronic Edition (link) BibTeX
- Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai:
Improved Results for Data Migration and Open Shop Scheduling.
658-669
Electronic Edition (link) BibTeX
- Leszek Gasieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin:
Deterministic M2M Multicast in Radio Networks: (Extended Abstract).
670-682
Electronic Edition (link) BibTeX
- Dan R. Ghica, Andrzej S. Murawski, C.-H. Luke Ong:
Syntactic Control of Concurrency.
683-694
Electronic Edition (link) BibTeX
- Venkatesan Guruswami, Piotr Indyk:
Linear-Time List Decoding in Error-Free Settings: (Extended Abstract).
695-707
Electronic Edition (link) BibTeX
- Esfandiar Haghverdi, Philip J. Scott:
A Categorical Model for the Geometry of Interaction.
708-720
Electronic Edition (link) BibTeX
- Shirley Halevy, Eyal Kushilevitz:
Testing Monotonicity over Graph Products.
721-732
Electronic Edition (link) BibTeX
- Eran Halperin, Richard M. Karp:
The Minimum-Entropy Set Cover Problem.
733-744
Electronic Edition (link) BibTeX
- Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, Srinivasan Venkatesh:
Communication Versus Computation.
745-756
Electronic Edition (link) BibTeX
- Brent Heeringa, Micah Adler:
Optimal Website Design with the Constrained Subtree Selection Problem.
757-769
Electronic Edition (link) BibTeX
- Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff:
Simple Permutations Mix Well.
770-781
Electronic Edition (link) BibTeX
- Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, Ely Porat:
Closest Pair Problems in Very High Dimensions.
782-792
Electronic Edition (link) BibTeX
- Emmanuel Jeandel:
Universality in Quantum Computation.
793-804
Electronic Edition (link) BibTeX
- Raja Jothi, Balaji Raghavachari:
Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design.
805-818
Electronic Edition (link) BibTeX
- Bala Kalyanasundaram, Mahendran Velauthapillai:
Fairness to All While Downsizing.
819-830
Electronic Edition (link) BibTeX
- Shin-ya Katsumata:
A Generalisation of Pre-logical Predicates to Simply Typed Formal Systems.
831-845
Electronic Edition (link) BibTeX
- Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch:
A Faster Algorithm for Minimum Cycle Basis of Graphs.
846-857
Electronic Edition (link) BibTeX
- Robert Krauthgamer, James R. Lee:
The Black-Box Complexity of Nearest Neighbor Search.
858-869
Electronic Edition (link) BibTeX
- Michal Kunc:
Regular Solutions of Language Inequalities and Well Quasi-orders.
870-881
Electronic Edition (link) BibTeX
- James Laird:
A Calculus of Coroutines.
882-893
Electronic Edition (link) BibTeX
- Emmanuelle Lebhar, Nicolas Schabanel:
Almost Optimal Decentralized Routing in Long-Range Contact Networks.
894-905
Electronic Edition (link) BibTeX
- Markus Lohrey:
Word Problems on Compressed Words.
906-918
Electronic Edition (link) BibTeX
- Rune B. Lyngsø:
Complexity of Pseudoknot Prediction in Simple Models.
919-931
Electronic Edition (link) BibTeX
- Frédéric Magniez, Michel de Rougemont:
Property Testing of Regular Tree Languages.
932-944
Electronic Edition (link) BibTeX
- Keye Martin:
Entropy as a Fixed Point.
945-958
Electronic Edition (link) BibTeX
- Klaus Meer:
Transparent Long Proofs: A First PCP Theorem for NPR.
959-970
Electronic Edition (link) BibTeX
- Dieter van Melkebeek, Ran Raz:
A Time Lower Bound for Satisfiability.
971-982
Electronic Edition (link) BibTeX
- Wolfgang Merkle, Nenad Mihailovic, Theodore A. Slaman:
Some Results on Effective Randomness.
983-995
Electronic Edition (link) BibTeX
- Gatis Midrijanis:
A Polynomial Quantum Query Lower Bound for the Set Equality Problem.
996-1005
Electronic Edition (link) BibTeX
- J. Ian Munro, S. Srinivasa Rao:
Succinct Representations of Functions.
1006-1015
Electronic Edition (link) BibTeX
- Markus Müller-Olm, Helmut Seidl:
A Note on Karr's Algorithm.
1016-1028
Electronic Edition (link) BibTeX
- Sotiris E. Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis:
The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs.
1029-1040
Electronic Edition (link) BibTeX
- Rafail Ostrovsky, Charles Rackoff, Adam Smith:
Efficient Consistency Proofs for Generalized Queries on a Committed Database.
1041-1053
Electronic Edition (link) BibTeX
- Katarzyna E. Paluch:
A 2(1/8)-Approximation Algorithm for Rectangle Tiling.
1054-1065
Electronic Edition (link) BibTeX
- Grigore Rosu:
Extensional Theories and Rewriting.
1066-1079
Electronic Edition (link) BibTeX
- Süleyman Cenk Sahinalp, Andrey Utis:
Hardness of String Similarity Search and Other Indexing Problems.
1080-1098
Electronic Edition (link) BibTeX
- Marko Samer, Helmut Veith:
A Syntactic Characterization of Distributive LTL Queries.
1099-1110
Electronic Edition (link) BibTeX
- Peter Sanders, Naveen Sivadasan, Martin Skutella:
Online Scheduling with Bounded Migration.
1111-1122
Electronic Edition (link) BibTeX
- Nicole Schweikardt:
On the Expressive Power of Monadic Least Fixed Point Logic.
1123-1135
Electronic Edition (link) BibTeX
- Helmut Seidl, Thomas Schwentick, Anca Muscholl, Peter Habermehl:
Counting in Trees for Free.
1136-1149
Electronic Edition (link) BibTeX
- Olivier Serre:
Games with Winning Conditions of High Borel Complexity.
1150-1162
Electronic Edition (link) BibTeX
- Alan Skelley:
Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas.
1163-1175
Electronic Edition (link) BibTeX
- Michael Soltys:
LA, Permutations, and the Hajós Calculus.
1176-1187
Electronic Edition (link) BibTeX
- Michael Toftdal:
A Calibration of Ineffective Theorems of Analysis in a Hierarchy of Semi-classical Logical Principles: (Extended Abstract).
1188-1200
Electronic Edition (link) BibTeX
- Sergei Vassilvitskii, Mihalis Yannakakis:
Efficiently Computing Succinct Trade-Off Curves.
1201-1213
Electronic Edition (link) BibTeX
- Hagen Völzer:
On Randomization Versus Synchronization in Distributed Systems.
1214-1226
Electronic Edition (link) BibTeX
- Ryan Williams:
A New Algorithm for Optimal Constraint Satisfaction and Its Implications.
1227-1237
Electronic Edition (link) BibTeX
- Shengyu Zhang:
On the Power of Ambainis's Lower Bounds.
1238-1250
Electronic Edition (link) BibTeX
Copyright © Sat May 16 23:16:07 2009
by Michael Ley (ley@uni-trier.de)
