Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID31st ICALP 2004: Turku, Finland
- Josep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella:
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
Invited Talks
- Robert Harper:
Self-Adjusting Computation. 1-2 - Monika 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 Gordon 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, Raissa 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, Jirí 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 Dvorák, 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 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 - 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 2O(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 A. 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 NPR. 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 L. 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 D. 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
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-05-19 01:05 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
