31. ICALP 2004: Turku, Finland

Invited Talks

• Robert Harper:
  Self-Adjusting Computation. 1-2
  
• Monika Rauch Henzinger:
  The Past, Present, and Future of Web Search Engines p. 3
  
• Martin Hofmann:
  What Do Program Logics and Type Systems Have in Common? 4-7
  
• Alexander A. Razborov:
  Feasible Proofs and Computations: Partnership and Fusion. 8-14
  
• Wojciech Rytter:
  Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input. 15-27
  
• Mihalis Yannakakis:
  Testing, Optimizaton, and Games. 28-45
  

Contributed Papers

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