default search action
32nd ICALP 2005: Lisbon, Portugal
- Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, Moti Yung:
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
Invited Lectures
- Leslie G. Valiant:
Holographic Circuits. 1-15 - Anupam Datta, Ante Derek, John C. Mitchell, Vitaly Shmatikov, Mathieu Turuani:
Probabilistic Polynomial-Time Semantics for a Protocol Security Logic. 16-29 - Giuseppe Castagna, Alain Frisch:
A Gentle Introduction to Semantic Subtyping. 30-34 - Leonid Libkin:
Logics for Unranked Trees: An Overview. 35-50 - Martin Gairing, Thomas Lücking, Burkhard Monien, Karsten Tiemann:
Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture. 51-65
Data Structures I
- Philip Bille, Inge Li Gørtz:
The Tree Inclusion Problem: In Optimal Space and Faster. 66-77 - Stephen Alstrup, Inge Li Gørtz, Theis Rauhe, Mikkel Thorup, Uri Zwick:
Union-Find with Constant Time Deletions. 78-89 - Gianni Franceschini, Roberto Grossi:
Optimal In-place Sorting of Vectors and Records. 90-102 - Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter Sanders:
Towards Optimal Multiple Selection. 103-114
Cryptography and Complexity
- Marius Zimand:
Simple Extractors via Constructions of Cryptographic Pseudo-random Generators. 115-127 - Omer Horvitz, Jonathan Katz:
Bounds on the Efficiency of "Black-Box" Commitment Schemes. 128-139 - Hoeteck Wee:
On Round-Efficient Argument Systems. 140-152 - Roberto Tamassia, Nikos Triandopoulos:
Computational Bounds on Hierarchical Data Processing with Applications to Information Security. 153-165
Data Structures II
- Martin Dietzfelbinger, Christoph Weidling:
Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins. 166-178 - Ehsan Chiniforooshan, Arash Farzan, Mehdi Mirzazadeh:
Worst Case Optimal Union-Intersection Expression Evaluation. 179-190 - Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch:
Measure and Conquer: Domination - A Case Study. 191-203
Cryptography and Distributed Systems
- Klaus Kursawe, Victor Shoup:
Optimistic Asynchronous Atomic Broadcast. 204-215 - Giovanni Di Crescenzo, Aggelos Kiayias:
Asynchronous Perfectly Secure Communication over One-Time Pads. 216-227 - Giuseppe Persiano, Ivan Visconti:
Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds. 228-240
Graph Algorithms I
- Miroslaw Kowaluk, Andrzej Lingas:
LCA Queries in Directed Acyclic Graphs. 241-248 - Liam Roditty, Uri Zwick:
Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs. 249-260 - Liam Roditty, Mikkel Thorup, Uri Zwick:
Deterministic Constructions of Approximate Distance Oracles and Spanners. 261-272 - Telikepalli Kavitha:
An Õ(m2n) Randomized Algorithm to Compute a Minimum Cycle Basis of a Directed Graph. 273-284
Security Mechanisms
- Tal Moran, Moni Naor:
Basing Cryptographic Protocols on Tamper-Evident Seals. 285-297 - Dario Catalano, Ivan Visconti:
Hybrid Trapdoor Commitments and Their Applications. 298-310 - Nicholas Hopper:
On Steganographic Chosen Covertext Security. 311-323 - 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
Graph Algorithms II
- Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, David Peleg:
Label-Guided Graph Exploration by a Finite Automaton. 335-346 - Bogdan S. Chlebus, Leszek Gasieniec, Dariusz R. Kowalski, Tomasz Radzik
:
On the Wake-Up Problem in Radio Networks. 347-359 - Jirí Fiala, Petr A. Golovach, Jan Kratochvíl:
Distance Constrained Labelings of Graphs of Bounded Treewidth. 360-372 - Qian-Ping Gu, Hisao Tamaki:
Optimal Branch-Decomposition of Planar Graphs in O(n3) Time. 373-384
Automata and Formal Languages I
- Juraj Hromkovic, Georg Schnitger:
NFAs With and Without epsilon-Transitions. 385-396 - Marie-Pierre Béal, Sylvain Lombardy, Jacques Sakarovitch:
On the Equivalence of -Automata. 397-409 - Eugen Czeizler
A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata. 410-420 - Martin Beaudry, François Lemieux, Denis Thérien:
Groupoids That Recognize Only Regular Languages. 421-433
Signature and Message Authentication
- Eike Kiltz
Append-Only Signatures. 434-445 - Mårten Trolin, Douglas Wikström:
Hierarchical Group Signatures. 446-458 - Helger Lipmaa, Guilin Wang, Feng Bao:
Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction. 459-471 - Ueli M. Maurer, Johan Sjödin:
Single-Key AIL-MACs from Any FIL-MAC. 472-484
Algorithmic Game Theory
- Li Zhang:
The Efficiency and Fairness of a Fixed Budget Resource Allocation Game. 485-496 - Henry C. Lin, Tim Roughgarden, Éva Tardos, Asher Walkover:
Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability. 497-512
Automata and Logic
- Manfred Droste, Paul Gastin:
Weighted Automata and Weighted Logics. 513-525 - Pascal Tesson, Denis Thérien:
Restricted Two-Variable Sentences, Circuits and Communication Complexity. 526-538
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 y2=x2k+1+ax. 539-550 - Neeraj Kayal:
Solvability of a System of Bivariate Polynomial Equations over a Finite Field. 551-562
Cache-Oblivious Algorithms and Algorithmic Engineering
- Hema Jampala, Norbert Zeh:
Cache-Oblivious Planar Shortest Paths. 563-575 - Gerth Stølting Brodal
Cache-Aware and Cache-Oblivious Adaptive Sorting. 576-588 - Ingo Wegener:
Simulated Annealing Beats Metropolis in Combinatorial Optimization. 589-601
On-line Algorithms
- Leah Epstein, Meital Levy:
Online Interval Coloring and Variants. 602-613 - Wun-Tat Chan, Tak Wah Lam, Prudence W. H. Wong
Dynamic Bin Packing of Unit Fractions Items. 614-626 - Matthias Englert, Matthias Westermann:
Reordering Buffer Management for Non-uniform Cost Models. 627-638
Security Protocols Logic
- Yannick Chevalier, Michaël Rusinowitch:
Combining Intruder Theories. 639-651 - Mathieu Baudet
Computationally Sound Implementations of Equational Theories Against Passive Adversaries. 652-663 - Martín Abadi, Bogdan Warinschi:
Password-Based Encryption Analyzed. 664-676
Random Graphs
- Chen Avin, Gunes Ercal:
On the Cover Time of Random Geometric Graphs. 677-689 - Charilaos Efthymiou, Paul G. Spirakis:
On the Existence of Hamiltonian Cycles in Random Intersection Graphs. 690-701 - Nedialko B. Dimitrov, C. Greg Plaxton:
Optimal Cover Time for a Graph-Based Coupon Collector Process. 702-716 - Debora Donato, Stefano Leonardi, Panayiotis Tsaparas:
Stability and Similarity of Link Analysis Ranking Algorithms. 717-729
Concurrency I
- Damien Pous
Up-to Techniques for Weak Bisimulation. 730-741 - Éric Badouel, Jules Chenou, Goulven Guillou:
Petri Algebras. 742-754 - Wan J. Fokkink, Sumit Nain:
A Finite Basis for Failure Semantics. 755-765 - Giovanni Conforti, Damiano Macedonio, Vladimiro Sassone:
Spatial Logics for Bigraphs. 766-778
Encryption and related Primitives
- Marc Fischlin:
Completely Non-malleable Schemes. 779-790 - David Galindo:
Boneh-Franklin Identity Based Encryption Revisited. 791-802 - Craig Gentry, Zulfikar Ramzan:
Single-Database Private Information Retrieval with Constant Communication Rate. 803-815 - Giovanni Di Crescenzo, Ivan Visconti:
Concurrent Zero Knowledge in the Public-Key Model. 816-827
Approximation Algorithms I
- Martin Gairing, Burkhard Monien, Andreas Woclaw:
A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines. 828-839 - Annamária Kovács:
Polynomial Time Preemptive Sum-Multicoloring on Paths. 840-852 - Kamal Jain, Mohammad Taghi Hajiaghayi, Kunal Talwar:
The Generalized Deadlock Resolution Problem. 853-865 - Mihai Badoiu, Artur Czumaj, Piotr Indyk, Christian Sohler:
Facility Location in Sublinear Time. 866-877
Games
- Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger:
The Complexity of Stochastic Rabin and Streett Games'. 878-890 - Kousha Etessami, Mihalis Yannakakis:
Recursive Markov Decision Processes and Recursive Stochastic Games. 891-903 - James Laird
Decidability in Syntactic Control of Interference. 904-916 - Andrzej S. Murawski, C.-H. Luke Ong
Idealized Algol with Ground Recursion, and DPDA Equivalence. 917-929
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 - Allan Borodin, David Cashman, Avner Magen:
How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. 943-955 - Gustav Hast:
Approximating - Outperforming a Random Assignment with Almost a Linear Factor. 956-968
Lower Bounds
- Corina E. Patrascu, Mihai Patrascu:
On Dynamic Bit-Probe Complexity. 969-981 - Scott Diehl, Dieter van Melkebeek:
Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. 982-993 - Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen:
Lower Bounds for Circuits with Few Modular and Symmetric Gates. 994-1005
Probability
- Michael W. Mislove
Discrete Random Variables over Domains. 1006-1017 - Franck van Breugel, Claudio Hermida, Michael Makkai, James Worrell:
An Accessible Approach to Behavioural Pseudometrics. 1018-1030 - Eugene Asarin
Noisy Turing Machines. 1031-1042
Approximation Algorithms III
- George Karakostas
A Better Approximation Ratio for the Vertex Cover Problem. 1043-1050 - Anupam Gupta, Martin Pál:
Stochastic Steiner Trees Without a Root. 1051-1063 - Sriram V. Pemmaraju, Rajiv Raman:
Approximation Algorithms for the Max-coloring Problem. 1064-1075
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 - Parosh Aziz Abdulla, Johann Deneux, Joël Ouaknine, James Worrell:
Decidability and Complexity Results for Timed Automata via Channel Machines. 1089-1101 - Rajeev Alur, Viraj Kumar
Congruences for Visibly Pushdown Languages. 1102-1114
Approximation Algorithms IV
- Khaled M. Elbassioni
Approximation Algorithms for Euclidean Group TSP. 1115-1126 - David Kempe, Jon M. Kleinberg, Éva Tardos:
Influential Nodes in a Diffusion Model for Social Networks. 1127-1138 - Christoph Ambühl:
An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks. 1139-1150 - Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo, Martin Skutella:
New Approaches for Virtual Private Network Design. 1151-1162
Algebraic Computation and Communication Complexity
- Jeff Ford, Anna Gál:
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity. 1163-1175 - Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. 1176-1188 - Douglas Wikström:
On the l-Ary GCD-Algorithm in Rings of Integers. 1189-1201
Concurrency II
- Michael Baldamus, Joachim Parrow, Björn Victor:
A Fully Abstract Encoding of the pi-Calculus with Data Terms. 1202-1213 - Mohammad Reza Mousavi, Michel A. Reniers:
Orthogonal Extensions in Structural Operational Semantics. 1214-1225 - Rocco De Nicola
Basic Observables for a Calculus for Global Computing. 1226-1238 - Giorgio Delzanno, Maurizio Gabbrielli
Compositional Verification of Asynchronous Processes via Constraint Solving. 1239-1250
String Matching and Computational Biology
- Martin Farach-Colton
Optimal Spaced Seeds for Faster Approximate String Matching. 1251-1262 - Isaac Elias, Jens Lagergren:
Fast Neighbor Joining. 1263-1274 - Ming-Yang Kao, Manan Sanghi, Robert T. Schweller:
Randomized Fast Design of Short DNA Words. 1275-1286
Quantum Complexity
- Pascal Koiran, Vincent Nesme, Natacha Portier:
A Quantum Lower Bound for the Query Complexity of Simon's Problem. 1287-1298 - Robert Spalek, Mario Szegedy:
All Quantum Adversary Methods Are Equivalent. 1299-1311 - Frédéric Magniez, Ashwin Nayak:
Quantum Complexity of Testing Group Commutativity. 1312-1324
Analysis and Verification
- Mila Dalla Preda, Roberto Giacobazzi:
Semantic-Based Code Obfuscation by Abstract Interpretation. 1325-1336 - Bernhard Reus, Thomas Streicher:
About Hoare Logics for Higher-Order Store. 1337-1348 - Aaron R. Bradley, Zohar Manna, Henny B. Sipma:
The Polyranking Principle. 1349-1361
Geometry and Load Balancing
- Bengt J. Nilsson:
Approximate Guarding of Monotone and Rectilinear Polygons. 1362-1373 - Amit Kumar
Linear Time Algorithms for Clustering Problems in Any Dimensions. 1374-1385 - Petra Berenbrink, Tom Friedetzky, Russell A. Martin:
Dynamic Diffusion Load Balancing. 1386-1398
Concrete Complexity and Codes
- Jaikumar Radhakrishnan, Martin Rötteler
On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group. 1399-1411 - (Withdrawn) On the Hardness of Embeddings Between Two Finite Metrics. 1412-1423
- Stephanie Wehner, Ronald de Wolf:
Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval. 1424-1436
Model Theory and Model Checking
- Albert Atserias, Anuj Dawar
Preservation Under Extensions on Well-Behaved Finite Structures. 1437-1449 - Teodor Knapik, Damian Niwinski, Pawel Urzyczyn, Igor Walukiewicz:
Unsafe Grammars and Panic Automata. 1450-1461 - Cheng Li, Zhe Dang, Oscar H. Ibarra, Hsu-Chun Yen:
Signaling P Systems and Verification Problems. 1462-1473
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-11-15 19:44 CET 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: