32. ICALP 2005: Lisbon, Portugal

Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, Moti Yung (Eds.): Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings. Lecture Notes in Computer Science 3580 Springer 2005, ISBN 3-540-27580-0 BibTeX

Invited Lectures

Leslie G. Valiant:
Holographic Circuits. 1-15
Electronic Edition (link) BibTeX
Anupam Datta, Ante Derek, John C. Mitchell, Vitaly Shmatikov, Mathieu Turuani:
Probabilistic Polynomial-Time Semantics for a Protocol Security Logic. 16-29
Electronic Edition (link) BibTeX
Giuseppe Castagna, Alain Frisch:
A Gentle Introduction to Semantic Subtyping. 30-34
Electronic Edition (link) BibTeX
Leonid Libkin:
Logics for Unranked Trees: An Overview. 35-50
Electronic Edition (link) BibTeX
Martin Gairing, Thomas Lücking, Burkhard Monien, Karsten Tiemann:
Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture. 51-65
Electronic Edition (link) BibTeX

Data Structures I

Philip Bille, Inge Li Gørtz:
The Tree Inclusion Problem: In Optimal Space and Faster. 66-77
Electronic Edition (link) BibTeX
Stephen Alstrup, Inge Li Gørtz, Theis Rauhe, Mikkel Thorup, Uri Zwick:
Union-Find with Constant Time Deletions. 78-89
Electronic Edition (link) BibTeX
Gianni Franceschini, Roberto Grossi:
Optimal In-place Sorting of Vectors and Records. 90-102
Electronic Edition (link) BibTeX
Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter Sanders:
Towards Optimal Multiple Selection. 103-114
Electronic Edition (link) BibTeX

Cryptography and Complexity

Marius Zimand:
Simple Extractors via Constructions of Cryptographic Pseudo-random Generators. 115-127
Electronic Edition (link) BibTeX
Omer Horvitz, Jonathan Katz:
Bounds on the Efficiency of "Black-Box" Commitment Schemes. 128-139
Electronic Edition (link) BibTeX
Hoeteck Wee:
On Round-Efficient Argument Systems. 140-152
Electronic Edition (link) BibTeX
Roberto Tamassia, Nikos Triandopoulos:
Computational Bounds on Hierarchical Data Processing with Applications to Information Security. 153-165
Electronic Edition (link) BibTeX

Data Structures II

Martin Dietzfelbinger, Christoph Weidling:
Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins. 166-178
Electronic Edition (link) BibTeX
Ehsan Chiniforooshan, Arash Farzan, Mehdi Mirzazadeh:
Worst Case Optimal Union-Intersection Expression Evaluation. 179-190
Electronic Edition (link) BibTeX
Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch:
Measure and Conquer: Domination - A Case Study. 191-203
Electronic Edition (link) BibTeX

Cryptography and Distributed Systems

Klaus Kursawe, Victor Shoup:
Optimistic Asynchronous Atomic Broadcast. 204-215
Electronic Edition (link) BibTeX
Giovanni Di Crescenzo, Aggelos Kiayias:
Asynchronous Perfectly Secure Communication over One-Time Pads. 216-227
Electronic Edition (link) BibTeX
Giuseppe Persiano, Ivan Visconti:
Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds. 228-240
Electronic Edition (link) BibTeX

Graph Algorithms I

Miroslaw Kowaluk, Andrzej Lingas:
LCA Queries in Directed Acyclic Graphs. 241-248
Electronic Edition (link) BibTeX
Liam Roditty, Uri Zwick:
Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs. 249-260
Electronic Edition (link) BibTeX
Liam Roditty, Mikkel Thorup, Uri Zwick:
Deterministic Constructions of Approximate Distance Oracles and Spanners. 261-272
Electronic Edition (link) BibTeX
Telikepalli Kavitha:
An Õ(m²n) Randomized Algorithm to Compute a Minimum Cycle Basis of a Directed Graph. 273-284
Electronic Edition (link) BibTeX

Security Mechanisms

Tal Moran, Moni Naor:
Basing Cryptographic Protocols on Tamper-Evident Seals. 285-297
Electronic Edition (link) BibTeX
Dario Catalano, Ivan Visconti:
Hybrid Trapdoor Commitments and Their Applications. 298-310
Electronic Edition (link) BibTeX
Nicholas Hopper:
On Steganographic Chosen Covertext Security. 311-323
Electronic Edition (link) BibTeX
An Braeken, Yuri L. Borissov, Svetla Nikova, Bart Preneel:
Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties. 324-334
Electronic Edition (link) BibTeX

Graph Algorithms II

Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, David Peleg:
Label-Guided Graph Exploration by a Finite Automaton. 335-346
Electronic Edition (link) BibTeX
Bogdan S. Chlebus, Leszek Gasieniec, Dariusz R. Kowalski, Tomasz Radzik:
On the Wake-Up Problem in Radio Networks. 347-359
Electronic Edition (link) BibTeX
Jirí Fiala, Petr A. Golovach, Jan Kratochvíl:
Distance Constrained Labelings of Graphs of Bounded Treewidth. 360-372
Electronic Edition (link) BibTeX
Qian-Ping Gu, Hisao Tamaki:
Optimal Branch-Decomposition of Planar Graphs in O(n³) Time. 373-384
Electronic Edition (link) BibTeX

Automata and Formal Languages I

Juraj Hromkovic, Georg Schnitger:
NFAs With and Without epsilon-Transitions. 385-396
Electronic Edition (link) BibTeX
Marie-Pierre Béal, Sylvain Lombardy, Jacques Sakarovitch:
On the Equivalence of -Automata. 397-409
Electronic Edition (link) BibTeX
Eugen Czeizler, Jarkko Kari:
A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata. 410-420
Electronic Edition (link) BibTeX
Martin Beaudry, François Lemieux, Denis Thérien:
Groupoids That Recognize Only Regular Languages. 421-433
Electronic Edition (link) BibTeX

Signature and Message Authentication

Eike Kiltz, Anton Mityagin, Saurabh Panjwani, Barath Raghavan:
Append-Only Signatures. 434-445
Electronic Edition (link) BibTeX
Mårten Trolin, Douglas Wikström:
Hierarchical Group Signatures. 446-458
Electronic Edition (link) BibTeX
Helger Lipmaa, Guilin Wang, Feng Bao:
Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction. 459-471
Electronic Edition (link) BibTeX
Ueli M. Maurer, Johan Sjödin:
Single-Key AIL-MACs from Any FIL-MAC. 472-484
Electronic Edition (link) BibTeX

Algorithmic Game Theory

Li Zhang:
The Efficiency and Fairness of a Fixed Budget Resource Allocation Game. 485-496
Electronic Edition (link) BibTeX
Henry Lin, Tim Roughgarden, Éva Tardos, Asher Walkover:
Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability. 497-512
Electronic Edition (link) BibTeX

Automata and Logic

Manfred Droste, Paul Gastin:
Weighted Automata and Weighted Logics. 513-525
Electronic Edition (link) BibTeX
Pascal Tesson, Denis Thérien:
Restricted Two-Variable Sentences, Circuits and Communication Complexity. 526-538
Electronic Edition (link) BibTeX

Computational Algebra

Mitsuhiro Haneda, Mitsuru Kawazoe, Tetsuya Takahashi:
Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of Type y²=x^2k+1+ax. 539-550
Electronic Edition (link) BibTeX
Neeraj Kayal:
Solvability of a System of Bivariate Polynomial Equations over a Finite Field. 551-562
Electronic Edition (link) BibTeX

Cache-Oblivious Algorithms and Algorithmic Engineering

Hema Jampala, Norbert Zeh:
Cache-Oblivious Planar Shortest Paths. 563-575
Electronic Edition (link) BibTeX
Gerth Stølting Brodal, Rolf Fagerberg, Gabriel Moruz:
Cache-Aware and Cache-Oblivious Adaptive Sorting. 576-588
Electronic Edition (link) BibTeX
Ingo Wegener:
Simulated Annealing Beats Metropolis in Combinatorial Optimization. 589-601
Electronic Edition (link) BibTeX

On-line Algorithms

Leah Epstein, Meital Levy:
Online Interval Coloring and Variants. 602-613
Electronic Edition (link) BibTeX
Wun-Tat Chan, Tak Wah Lam, Prudence W. H. Wong:
Dynamic Bin Packing of Unit Fractions Items. 614-626
Electronic Edition (link) BibTeX
Matthias Englert, Matthias Westermann:
Reordering Buffer Management for Non-uniform Cost Models. 627-638
Electronic Edition (link) BibTeX

Security Protocols Logic

Yannick Chevalier, Michaël Rusinowitch:
Combining Intruder Theories. 639-651
Electronic Edition (link) BibTeX
Mathieu Baudet, Véronique Cortier, Steve Kremer:
Computationally Sound Implementations of Equational Theories Against Passive Adversaries. 652-663
Electronic Edition (link) BibTeX
Martín Abadi, Bogdan Warinschi:
Password-Based Encryption Analyzed. 664-676
Electronic Edition (link) BibTeX

Random Graphs

Chen Avin, Gunes Ercal:
On the Cover Time of Random Geometric Graphs. 677-689
Electronic Edition (link) BibTeX
Charilaos Efthymiou, Paul G. Spirakis:
On the Existence of Hamiltonian Cycles in Random Intersection Graphs. 690-701
Electronic Edition (link) BibTeX
Nedialko B. Dimitrov, C. Greg Plaxton:
Optimal Cover Time for a Graph-Based Coupon Collector Process. 702-716
Electronic Edition (link) BibTeX
Debora Donato, Stefano Leonardi, Panayiotis Tsaparas:
Stability and Similarity of Link Analysis Ranking Algorithms. 717-729
Electronic Edition (link) BibTeX

Concurrency I

Damien Pous:
Up-to Techniques for Weak Bisimulation. 730-741
Electronic Edition (link) BibTeX
Eric Badouel, Jules Chenou, Goulven Guillou:
Petri Algebras. 742-754
Electronic Edition (link) BibTeX
Wan Fokkink, Sumit Nain:
A Finite Basis for Failure Semantics. 755-765
Electronic Edition (link) BibTeX
Giovanni Conforti, Damiano Macedonio, Vladimiro Sassone:
Spatial Logics for Bigraphs. 766-778
Electronic Edition (link) BibTeX

Encryption and related Primitives

Marc Fischlin:
Completely Non-malleable Schemes. 779-790
Electronic Edition (link) BibTeX
David Galindo:
Boneh-Franklin Identity Based Encryption Revisited. 791-802
Electronic Edition (link) BibTeX
Craig Gentry, Zulfikar Ramzan:
Single-Database Private Information Retrieval with Constant Communication Rate. 803-815
Electronic Edition (link) BibTeX
Giovanni Di Crescenzo, Ivan Visconti:
Concurrent Zero Knowledge in the Public-Key Model. 816-827
Electronic Edition (link) BibTeX

Approximation Algorithms I

Martin Gairing, Burkhard Monien, Andreas Woclaw:
A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines. 828-839
Electronic Edition (link) BibTeX
Annamária Kovács:
Polynomial Time Preemptive Sum-Multicoloring on Paths. 840-852
Electronic Edition (link) BibTeX
Kamal Jain, Mohammad Taghi Hajiaghayi, Kunal Talwar:
The Generalized Deadlock Resolution Problem. 853-865
Electronic Edition (link) BibTeX
Mihai Badoiu, Artur Czumaj, Piotr Indyk, Christian Sohler:
Facility Location in Sublinear Time. 866-877
Electronic Edition (link) BibTeX

Games

Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger:
The Complexity of Stochastic Rabin and Streett Games'. 878-890
Electronic Edition (link) BibTeX
Kousha Etessami, Mihalis Yannakakis:
Recursive Markov Decision Processes and Recursive Stochastic Games. 891-903
Electronic Edition (link) BibTeX
James Laird:
Decidability in Syntactic Control of Interference. 904-916
Electronic Edition (link) BibTeX
Andrzej S. Murawski, C.-H. Luke Ong, Igor Walukiewicz:
Idealized Algol with Ground Recursion, and DPDA Equivalence. 917-929
Electronic Edition (link) BibTeX

Approximation Algorithms II

Jochen Könemann, Stefano Leonardi, Guido Schäfer, Stefan H. M. van Zwam:
From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem. 930-942
Electronic Edition (link) BibTeX
Allan Borodin, David Cashman, Avner Magen:
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. 943-955
Electronic Edition (link) BibTeX
Gustav Hast:
Approximating - Outperforming a Random Assignment with Almost a Linear Factor. 956-968
Electronic Edition (link) BibTeX

Lower Bounds

Corina E. Patrascu, Mihai Patrascu:
On Dynamic Bit-Probe Complexity. 969-981
Electronic Edition (link) BibTeX
Scott Diehl, Dieter van Melkebeek:
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. 982-993
Electronic Edition (link) BibTeX
Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen:
Lower Bounds for Circuits with Few Modular and Symmetric Gates. 994-1005
Electronic Edition (link) BibTeX

Probability

Michael W. Mislove:
Discrete Random Variables over Domains. 1006-1017
Electronic Edition (link) BibTeX
Franck van Breugel, Claudio Hermida, Michael Makkai, James Worrell:
An Accessible Approach to Behavioural Pseudometrics. 1018-1030
Electronic Edition (link) BibTeX
Eugene Asarin, Pieter Collins:
Noisy Turing Machines. 1031-1042
Electronic Edition (link) BibTeX

Approximation Algorithms III

George Karakostas:
A Better Approximation Ratio for the Vertex Cover Problem. 1043-1050
Electronic Edition (link) BibTeX
Anupam Gupta, Martin Pál:
Stochastic Steiner Trees Without a Root. 1051-1063
Electronic Edition (link) BibTeX
Sriram V. Pemmaraju, Rajiv Raman:
Approximation Algorithms for the Max-coloring Problem. 1064-1075
Electronic Edition (link) BibTeX

Automata and Formal Languages II

Martin Grohe, Christoph Koch, Nicole Schweikardt:
Tight Lower Bounds for Query Processing on Streaming and External Memory Data. 1076-1088
Electronic Edition (link) BibTeX
Parosh Aziz Abdulla, Johann Deneux, Joël Ouaknine, James Worrell:
Decidability and Complexity Results for Timed Automata via Channel Machines. 1089-1101
Electronic Edition (link) BibTeX
Rajeev Alur, Viraj Kumar, P. Madhusudan, Mahesh Viswanathan:
Congruences for Visibly Pushdown Languages. 1102-1114
Electronic Edition (link) BibTeX

Approximation Algorithms IV

Khaled M. Elbassioni, Aleksei V. Fishkin, Nabil H. Mustafa, René Sitters:
Approximation Algorithms for Euclidean Group TSP. 1115-1126
Electronic Edition (link) BibTeX
David Kempe, Jon M. Kleinberg, Éva Tardos:
Influential Nodes in a Diffusion Model for Social Networks. 1127-1138
Electronic Edition (link) BibTeX
Christoph Ambühl:
An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks. 1139-1150
Electronic Edition (link) BibTeX
Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo, Martin Skutella:
New Approaches for Virtual Private Network Design. 1151-1162
Electronic Edition (link) BibTeX

Algebraic Computation and Communication Complexity

Jeff Ford, Anna Gál:
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity. 1163-1175
Electronic Edition (link) BibTeX
Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. 1176-1188
Electronic Edition (link) BibTeX
Douglas Wikström:
On the l-Ary GCD-Algorithm in Rings of Integers. 1189-1201
Electronic Edition (link) BibTeX

Concurrency II

Michael Baldamus, Joachim Parrow, Björn Victor:
A Fully Abstract Encoding of the pi-Calculus with Data Terms. 1202-1213
Electronic Edition (link) BibTeX
Mohammad Reza Mousavi, Michel A. Reniers:
Orthogonal Extensions in Structural Operational Semantics. 1214-1225
Electronic Edition (link) BibTeX
Rocco De Nicola, Daniele Gorla, Rosario Pugliese:
Basic Observables for a Calculus for Global Computing. 1226-1238
Electronic Edition (link) BibTeX
Giorgio Delzanno, Maurizio Gabbrielli:
Compositional Verification of Asynchronous Processes via Constraint Solving. 1239-1250
Electronic Edition (link) BibTeX

String Matching and Computational Biology

Martin Farach-Colton, Gad M. Landau, Süleyman Cenk Sahinalp, Dekel Tsur:
Optimal Spaced Seeds for Faster Approximate String Matching. 1251-1262
Electronic Edition (link) BibTeX
Isaac Elias, Jens Lagergren:
Fast Neighbor Joining. 1263-1274
Electronic Edition (link) BibTeX
Ming-Yang Kao, Manan Sanghi, Robert T. Schweller:
Randomized Fast Design of Short DNA Words. 1275-1286
Electronic Edition (link) BibTeX

Quantum Complexity

Pascal Koiran, Vincent Nesme, Natacha Portier:
A Quantum Lower Bound for the Query Complexity of Simon's Problem. 1287-1298
Electronic Edition (link) BibTeX
Robert Spalek, Mario Szegedy:
All Quantum Adversary Methods Are Equivalent. 1299-1311
Electronic Edition (link) BibTeX
Frédéric Magniez, Ashwin Nayak:
Quantum Complexity of Testing Group Commutativity. 1312-1324
Electronic Edition (link) BibTeX

Analysis and Verification

Mila Dalla Preda, Roberto Giacobazzi:
Semantic-Based Code Obfuscation by Abstract Interpretation. 1325-1336
Electronic Edition (link) BibTeX
Bernhard Reus, Thomas Streicher:
About Hoare Logics for Higher-Order Store. 1337-1348
Electronic Edition (link) BibTeX
Aaron R. Bradley, Zohar Manna, Henny B. Sipma:
The Polyranking Principle. 1349-1361
Electronic Edition (link) BibTeX

Geometry and Load Balancing

Bengt J. Nilsson:
Approximate Guarding of Monotone and Rectilinear Polygons. 1362-1373
Electronic Edition (link) BibTeX
Amit Kumar, Yogish Sabharwal, Sandeep Sen:
Linear Time Algorithms for Clustering Problems in Any Dimensions. 1374-1385
Electronic Edition (link) BibTeX
Petra Berenbrink, Tom Friedetzky, Russell A. Martin:
Dynamic Diffusion Load Balancing. 1386-1398
Electronic Edition (link) BibTeX

Concrete Complexity and Codes

Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen:
On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group. 1399-1411
Electronic Edition (link) BibTeX
Matthew Cary, Atri Rudra, Ashish Sabharwal:
On the Hardness of Embeddings Between Two Finite Metrics. 1412-1423
Electronic Edition (link) BibTeX
Stephanie Wehner, Ronald de Wolf:
Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval. 1424-1436
Electronic Edition (link) BibTeX

Model Theory and Model Checking

Albert Atserias, Anuj Dawar, Martin Grohe:
Preservation Under Extensions on Well-Behaved Finite Structures. 1437-1449
Electronic Edition (link) BibTeX
Teodor Knapik, Damian Niwinski, Pawel Urzyczyn, Igor Walukiewicz:
Unsafe Grammars and Panic Automata. 1450-1461
Electronic Edition (link) BibTeX
Cheng Li, Zhe Dang, Oscar H. Ibarra, Hsu-Chun Yen:
Signaling P Systems and Verification Problems. 1462-1473
Electronic Edition (link) BibTeX