29. ICALP 2002: Málaga, Spain

Invited Talks

• John H. Reif:
  Molecular Assembly and Computation: From Theory to Experimental Demonstrations. 1-21
  
• Madhav V. Marathe:
  Towards a Predictive Computational Complexity Theory. 22-31
  
• Andrew M. Pitts:
  Equivariant Syntax and Semantics. 32-36
  
• Géraud Sénizergues:
  L(A) = L(B)? Decidability Results from Complete Formal Systems. 37
  
• Alberto Del Lungo, Andrea Frosini, Maurice Nivat, Laurent Vuillon:
  Discrete Tomography: Reconstruction under Periodicity Constraints. 38-56
  
• Heikki Mannila:
  Local and Global Methods in Data Mining: Basic Techniques and Open Problems. 57-68
  
• Manuel V. Hermenegildo, Germán Puebla, Francisco Bueno, Pedro López-García:
  Program Debugging and Validation Using Semantic Approximations and Partial Specifications. 69-72
  

Best Papers

• Lars Engebretsen, Jonas Holmerin, Alexander Russell:
  Inapproximability Results for Equations over Finite Groups. 73-84
  
• Seth Pettie:
  A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs. 85-97
  
• Thomas Colcombet:
  On Families of Graphs Having a Decidable First Order Theory with Reachability. 98-109
  

Contributions

• Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou:
  Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. 110-122
  
• Dimitris Fotakis, Spyros C. Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul G. Spirakis:
  The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. 123-134
  
• Sanjeev Khanna, Joseph Naor, Danny Raz:
  Control Message Aggregation in Group Communication Protocols. 135-146
  
• Tomasz Jurdzinski, Krzysztof Lorys:
  Church-Rosser Languages vs. UCFL. 147-158
  
• Sebastian Bala:
  Intersection of Regular Languages and Star Hierarchy. 159-169
  
• Sylvain Lombardy:
  On the Construction of Reversible Automata for Reversible Languages. 170-182
  
• Amr Elmasry:
  Priority Queues, Pairing, and Adaptive Sorting. 183-194
  
• Michael A. Bender, Richard Cole, Rajeev Raman:
  Exponential Structures for Efficient Cache-Oblivious Algorithms. 195-207
  
• Russell Impagliazzo, Nathan Segerlind:
  Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. 208-219
  
• Juan Luis Esteban, Nicola Galesi, Jochen Messner:
  On the Complexity of Resolution with Bounded Conjunctions. 220-231
  
• Aggelos Kiayias, Moti Yung:
  Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes. 232-243
  
• Yuval Ishai, Eyal Kushilevitz:
  Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials. 244-256
  
• Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik:
  Exponential Lower Bound for Static Semi-algebraic Proofs. 257-268
  
• Andreas Jakoby, Maciej Liskiewicz:
  Paths Problems in Symmetric Logarithmic Space. 269-280
  
• Peter Damaschke:
  Scheduling Search Procedures. 281-292
  
• Kazuo Iwama, Shiro Taketomi:
  Removable Online Knapsack Problems. 293-305
  
• Leah Epstein, Steven S. Seiden, Rob van Stee:
  New Bounds for Variable-Sized and Resource Augmented Online Bin Packing. 306-317
  
• Nicolas Ollinger:
  The Quest for Small Universal Cellular Automata. 318-329
  
• Christophe Papazian, Eric Rémila:
  Hyperbolic Recognition by Graph Automata. 330-342
  
• Farid M. Ablayev, Cristopher Moore, Chris Pollett:
  Quantum and Stochastic Branching Programs of Bounded Width. 343-354
  
• Luisa Gargano, Pavol Hell, Ladislav Stacho, Ugo Vaccaro:
  Spanning Trees with Bounded Number of Branch Vertices. 355-365
  
• René Beier, Peter Sanders, Naveen Sivadasan:
  Energy Optimal Routing in Radio Networks Using Geometric Data Structures. 366-376
  
• Malin Christersson, Leszek Gasieniec, Andrzej Lingas:
  Gossiping with Bounded Size Messages in ad hoc Radio Networks. 377-389
  
• Wolfgang Merkle:
  The Kolmogorov-Loveland Stochastic Sequences Are Not Closed under Selecting Subsequences. 390-400
  
• Robert A. Hearn, Erik D. Demaine:
  The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications. 401-413
  
• Víctor Dalmau:
  Constraint Satisfaction Problems in Non-deterministic Logarithmic Space. 414-425
  
• Gerth Stølting Brodal, Rolf Fagerberg:
  Cache Oblivious Distribution Sweeping. 426-438
  
• Anna Östlin, Rasmus Pagh:
  One-Probe Search. 439-450
  
• Moses Charikar, Piotr Indyk, Rina Panigrahy:
  New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems. 451-462
  
• Keye Martin, Michael W. Mislove, James Worrell:
  Measuring the Probabilistic Powerdomain. 463-475
  
• C.-H. Luke Ong, Pietro Di Gianantonio:
  Games Characterizing Levy-Longo Trees. 476-487
  
• Andrej Bauer, Martín Hötzel Escardó, Alex K. Simpson:
  Comparing Functional Paradigms for Exact Real-Number Computation. 488-500
  
• Philippe Duchon, Philippe Flajolet, Guy Louchard, Gilles Schaeffer:
  Random Sampling from Boltzmann Principles. 501-513
  
• Amalia Duch, Conrado Martínez:
  On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures. 514-524
  
• Marco Kick:
  Bialgebraic Modelling of Timed Processes. 525-536
  
• Franck van Breugel, Steven Shalit, James Worrell:
  Testing Labelled Markov Processes. 537-548
  
• John M. Hitchcock, Jack H. Lutz:
  Why Computational Complexity Requires Stricter Martingales. 549-560
  
• John M. Hitchcock:
  Correspondence Principles for Effective Dimensions. 561-571
  
• José Meseguer, Grigore Rosu:
  A Total Approach to Partial Algebraic Specification. 572-584
  
• Markus Lohrey, Pedro R. D'Argenio, Holger Hermanns:
  Axiomatising Divergence. 585-596
  
• Luca Cardelli, Philippa Gardner, Giorgio Ghelli:
  A Spatial Logic for Querying Graphs. 597-610
  
• Tomasz Radzik:
  Improving Time Bounds on Maximum Generalised Flow Computations by Contracting the Network. 611-622
  
• Piotr Berman, Marek Karpinski:
  Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. 623-632
  
• Camil Demetrescu, Giuseppe F. Italiano:
  Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths. 633-643
  
• Thomas A. Henzinger, Sriram C. Krishnan, Orna Kupferman, Freddy Y. C. Mang:
  Synthesis of Uninitialized Systems. 644-656
  
• Blaise Genest, Anca Muscholl, Helmut Seidl, Marc Zeitoun:
  Infinite-State High-Level MSCs: Model-Checking and Realizability. 657-668
  
• Klaus Wich:
  Universal Inherence of Cycle-Free Context-Free Ambiguity Functions. 669-680
  
• Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss:
  Histogramming Data Streams with Fast Per-Item Processing. 681-692
  
• Moses Charikar, Kevin Chen, Martin Farach-Colton:
  Finding Frequent Items in Data Streams. 693-703
  
• Thierry Cachat:
  Symbolic Strategy Synthesis for Games on Pushdown Graphs. 704-715
  
• Jirí Srba:
  Strong Bisimilarity and Regularity of Basic Process Algebra Is PSPACE-Hard. 716-727
  
• Gerth Stølting Brodal, Rune B. Lyngsø, Anna Östlin, Christian N. S. Pedersen:
  Solving the String Statistics Problem in Time O(n log n). 728-739
  
• Xiaotie Deng, Guojun Li, Zimao Li, Bin Ma, Lusheng Wang:
  A PTAS for Distinguishing (Sub)string Selection. 740-751
  
• Dietrich Kuske, Markus Lohrey:
  On the Theory of One-Step Rewriting in Trace Monoids. 752-763
  
• Michal Bielecki, Jan Hidders, Jan Paredaens, Jerzy Tyszkiewicz, Jan Van den Bussche:
  Navigating with a Browser. 764-775
  
• V. S. Anil Kumar, Madhav V. Marathe:
  Improved Results for Stackelberg Scheduling Strategies. 776-787
  
• Udo Adamy, Christoph Ambühl, R. Sai Anand, Thomas Erlebach:
  Call Control in Rings. 788-799
  
• Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob van Stee, Tomás Tichý, Nodari Vakhania:
  Preemptive Scheduling in Overloaded Systems. 800-811
  
• Juhani Karhumäki, Leonid P. Lisovik:
  The Equivalence Problem of Finite Substitutions on ab^*c, with Applications. 812-820
  
• Colin Stirling:
  Deciding DPDA Equivalence Is Primitive Recursive. 821-832
  
• Mikolaj Bojanczyk:
  Two-Way Alternating Automata and Finite Models. 833-844
  
• Piotr Berman, Marek Karpinski, Yakov Nekrich:
  Approximating Huffman Codes in Parallel. 845-855
  
• Carlo Fantozzi, Andrea Pietracaprina, Geppino Pucci:
  Seamless Integration of Parallelism and Memory Hierarchy. 856-867
  
• Noam Nisan:
  The Communication Complexity of Approximate Set Packing and Covering. 868-875
  
• Benjamin Doerr:
  Antirandomizing the Wrong Game. 876-887
  
• Karhan Akcoglu, Petros Drineas, Ming-Yang Kao:
  Fast Universalization of Investment Strategies with Provably Good Relative Returns. 888-900
  
• Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking:
  Randomized Pursuit-Evasion in Graphs. 901-912
  
• J. B. Wells:
  The Essence of Principal Typings. 913-925
  
• Bharat Adsul, Milind A. Sohoni:
  Complete and Tractable Local Linear Time Temporal Logics over Traces. 926-937
  
• Paul Gastin, Madhavan Mukund:
  An Elementary Expressively Complete Temporal Logic for Mazurkiewicz Traces. 938-949
  
• Vasco Brattka:
  Random Numbers and an Incomplete Immune Recursive Set. 950-961
  
• Peter Hertling:
  A Banach-Mazur Computable But Not Markov Computable Function on the Computable Real Numbers. 962-972
  
• Artur Czumaj, Andrzej Lingas, Hairong Zhao:
  Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem. 973-984
  
• Andreas Björklund, Thore Husfeldt:
  Finding a Path of Superlogarithmic Length. 985-992
  
• Ryuhei Uehara:
  Linear Time Algorithms on Chordal Bipartite and Strongly Chordal Graphs. 993-1004
  
• Jonas Holmerin:
  Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs. 1005-1016
  
• Yoshiharu Kohayakawa, Brendan Nagle, Vojtech Rödl:
  Efficient Testing of Hypergraphs. 1017-1028
  
• Xiaodong Wu, Danny Z. Chen:
  Optimal Net Surface Problems with Applications. 1029-1042
  
• Nicolas Bonichon, Bertrand Le Saëc, Mohamed Mosbah:
  Wagner's Theorem on Realizers. 1043-1053
  
• Vincenzo Liberatore:
  Circular Arrangements. 1054-1066