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. Springer 2004 Lecture Notes in Computer Science ISBN 3-540-22849-7
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
- 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
- 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
- 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
- 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
- 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
- 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
- Claudia Faggian: Interactive Observability in Ludics. 506-518
- 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 log2n 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
- Gianni Franceschini, Roberto Grossi: A General Technique for Managing Strings in Comparison-Driven Data Structures. 606-617
- 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
- Venkatesan Guruswami, Piotr Indyk: Linear-Time List Decoding in Error-Free Settings: (Extended Abstract). 695-707
- 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
- 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
- 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
- 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
- Keye Martin: Entropy as a Fixed Point. 945-958
- Klaus Meer: Transparent Long Proofs: A First PCP Theorem for NPR. 959-970
- 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
- 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team