Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, Moti Yung
Proceedings of the 32nd International Colloquium on Automata, Languages and Programming
ICALP, 2005.

@proceedings{ICALP-2005,
	address       = "Lisbon, Portugal",
	editor        = "Luís Caires and Giuseppe F. Italiano and Luís Monteiro and Catuscia Palamidessi and Moti Yung",
	isbn          = "3-540-27580-0",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 32nd International Colloquium on Automata, Languages and Programming}",
	volume        = 3580,
	year          = 2005,
}

Contents (118 items)

12 ×#bound
10 ×#graph
10 ×#on the
10 ×#problem
8 ×#algorithm
8 ×#approximate
8 ×#complexity
8 ×#performance
8 ×#random
6 ×#automaton

ICALP-2005-Valiant #artificial reality

Holographic Circuits (LGV), pp. 1–15.

ICALP-2005-DattaDMST #logic #polynomial #probability #protocol #security #semantics

Probabilistic Polynomial-Time Semantics for a Protocol Security Logic (AD, AD, JCM, VS, MT), pp. 16–29.

ICALP-2005-CastagnaF #semantics #type system

A Gentle Introduction to Semantic Subtyping (GC, AF), pp. 30–34.

ICALP-2005-Libkin #logic #overview #perspective

Logics for Unranked Trees: An Overview (LL), pp. 35–50.

ICALP-2005-GairingLMT #equilibrium #nash

Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture (MG, TL, BM, KT), pp. 51–65.

ICALP-2005-BilleG #performance #problem

The Tree Inclusion Problem: In Optimal Space and Faster (PB, ILG), pp. 66–77.

ICALP-2005-AlstrupGRTZ #constant

Union-Find with Constant Time Deletions (SA, ILG, TR, MT, UZ), pp. 78–89.

ICALP-2005-FranceschiniG #sorting

Optimal In-place Sorting of Vectors and Records (GF, RG), pp. 90–102.

ICALP-2005-KaligosiMMS #multi #towards

Towards Optimal Multiple Selection (KK, KM, JIM, PS), pp. 103–114.

ICALP-2005-Zimand #encryption #generative #pseudo

Simple Extractors via Constructions of Cryptographic Pseudo-random Generators (MZ), pp. 115–127.

ICALP-2005-HorvitzK #black box #bound #performance

Bounds on the Efficiency of “Black-Box” Commitment Schemes (OH, JK), pp. 128–139.

ICALP-2005-Wee #on the

On Round-Efficient Argument Systems (HW), pp. 140–152.

ICALP-2005-TamassiaT #bound #security

Computational Bounds on Hierarchical Data Processing with Applications to Information Security (RT, NT), pp. 153–165.

ICALP-2005-DietzfelbingerW #constant

Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins (MD, CW), pp. 166–178.

ICALP-2005-ChiniforooshanFM #evaluation

Worst Case Optimal Union-Intersection Expression Evaluation (EC, AF, MM), pp. 179–190.

ICALP-2005-FominGK #case study

Measure and Conquer: Domination — A Case Study (FVF, FG, DK), pp. 191–203.

ICALP-2005-KursaweS

Optimistic Asynchronous Atomic Broadcast (KK, VS), pp. 204–215.

ICALP-2005-CrescenzoK #communication

Asynchronous Perfectly Secure Communication over One-Time Pads (GDC, AK), pp. 216–227.

ICALP-2005-PersianoV #concurrent #constant

Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds (GP, IV), pp. 228–240.

ICALP-2005-KowalukL #graph #query

LCA Queries in Directed Acyclic Graphs (MK, AL), pp. 241–248.

ICALP-2005-RodittyZ #graph

Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs (LR, UZ), pp. 249–260.

ICALP-2005-RodittyTZ #approximate #distance

Deterministic Constructions of Approximate Distance Oracles and Spanners (LR, MT, UZ), pp. 261–272.

ICALP-2005-Kavitha #algorithm #graph #random

An Õ(m2n) Randomized Algorithm to Compute a Minimum Cycle Basis of a Directed Graph (TK), pp. 273–284.

ICALP-2005-MoranN #encryption #protocol

Basing Cryptographic Protocols on Tamper-Evident Seals (TM, MN), pp. 285–297.

ICALP-2005-CatalanoV #hybrid

Hybrid Trapdoor Commitments and Their Applications (DC, IV), pp. 298–310.

ICALP-2005-Hopper #on the #security

On Steganographic Chosen Covertext Security (NH), pp. 311–323.

ICALP-2005-BraekenBNP #classification #encryption

Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties (AB, YLB, SN, BP), pp. 324–334.

ICALP-2005-CohenFIKP #automaton #finite #graph

Label-Guided Graph Exploration by a Finite Automaton (RC, PF, DI, AK, DP), pp. 335–346.

ICALP-2005-ChlebusGKR #network #on the #problem

On the Wake-Up Problem in Radio Networks (BSC, LG, DRK, TR), pp. 347–359.

ICALP-2005-FialaGK #bound #distance #graph

Distance Constrained Labelings of Graphs of Bounded Treewidth (JF, PAG, JK), pp. 360–372.

ICALP-2005-GuT #graph

Optimal Branch-Decomposition of Planar Graphs in O(n3) Time (QPG, HT), pp. 373–384.

ICALP-2005-HromkovicS

NFAs With and Without epsilon-Transitions (JH, GS), pp. 385–396.

ICALP-2005-BealLS #equivalence #on the

On the Equivalence of -Automata (MPB, SL, JS), pp. 397–409.

ICALP-2005-CzeizlerK #automaton #bound #linear

A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata (EC, JK), pp. 410–420.

ICALP-2005-BeaudryLT #regular expression

Groupoids That Recognize Only Regular Languages (MB, FL, DT), pp. 421–433.

ICALP-2005-KiltzMPR

Append-Only Signatures (EK, AM, SP, BR), pp. 434–445.

ICALP-2005-TrolinW

Hierarchical Group Signatures (MT, DW), pp. 446–458.

ICALP-2005-LipmaaWB #security #verification

Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction (HL, GW, FB), pp. 459–471.

ICALP-2005-MaurerS

Single-Key AIL-MACs from Any FIL-MAC (UMM, JS), pp. 472–484.

ICALP-2005-Zhang #game studies #performance #resource management

The Efficiency and Fairness of a Fixed Budget Resource Allocation Game (LZ0), pp. 485–496.

ICALP-2005-LinRTW #exponential #fibonacci

Braess’s Paradox, Fibonacci Numbers, and Exponential Inapproximability (HCL, TR, ÉT, AW), pp. 497–512.

ICALP-2005-DrosteG #automaton #logic

Weighted Automata and Weighted Logics (MD, PG), pp. 513–525.

ICALP-2005-TessonT #communication #complexity #strict

Restricted Two-Variable Sentences, Circuits and Communication Complexity (PT, DT), pp. 526–538.

ICALP-2005-HanedaKT

Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of Type y2=x2k+1+ax (MH, MK, TT), pp. 539–550.

ICALP-2005-Kayal #equation #finite #polynomial

Solvability of a System of Bivariate Polynomial Equations over a Finite Field (NK), pp. 551–562.

ICALP-2005-JampalaZ

Cache-Oblivious Planar Shortest Paths (HJ, NZ), pp. 563–575.

ICALP-2005-BrodalFM #adaptation #sorting

Cache-Aware and Cache-Oblivious Adaptive Sorting (GSB, RF, GM), pp. 576–588.

ICALP-2005-Wegener #combinator #optimisation

Simulated Annealing Beats Metropolis in Combinatorial Optimization (IW), pp. 589–601.

ICALP-2005-EpsteinL #online

Online Interval Coloring and Variants (LE, ML), pp. 602–613.

ICALP-2005-ChanLW

Dynamic Bin Packing of Unit Fractions Items (WTC, TWL, PWHW), pp. 614–626.

ICALP-2005-EnglertW #cost analysis #modelling #order

Reordering Buffer Management for Non-uniform Cost Models (ME, MW), pp. 627–638.

ICALP-2005-ChevalierR

Combining Intruder Theories (YC, MR), pp. 639–651.

ICALP-2005-BaudetCK #equation #implementation

Computationally Sound Implementations of Equational Theories Against Passive Adversaries (MB, VC, SK), pp. 652–663.

ICALP-2005-AbadiW #encryption

Password-Based Encryption Analyzed (MA, BW), pp. 664–676.

ICALP-2005-AvinE #geometry #graph #on the #random

On the Cover Time of Random Geometric Graphs (CA, GE), pp. 677–689.

ICALP-2005-EfthymiouS #graph #on the #random

On the Existence of Hamiltonian Cycles in Random Intersection Graphs (CE, PGS), pp. 690–701.

ICALP-2005-DimitrovP #graph #process

Optimal Cover Time for a Graph-Based Coupon Collector Process (NBD, CGP), pp. 702–716.

ICALP-2005-DonatoLT #algorithm #analysis #ranking #similarity

Stability and Similarity of Link Analysis Ranking Algorithms (DD, SL, PT), pp. 717–729.

ICALP-2005-Pous #bisimulation

Up-to Techniques for Weak Bisimulation (DP), pp. 730–741.

ICALP-2005-BadouelCG #algebra #petri net

Petri Algebras (EB, JC, GG), pp. 742–754.

ICALP-2005-FokkinkN #finite #semantics

A Finite Basis for Failure Semantics (WF, SN), pp. 755–765.

ICALP-2005-ConfortiMS #graph #logic

Spatial Logics for Bigraphs (GC, DM, VS), pp. 766–778.

ICALP-2005-Fischlin

Completely Non-malleable Schemes (MF), pp. 779–790.

ICALP-2005-Galindo #encryption #revisited

Boneh-Franklin Identity Based Encryption Revisited (DG), pp. 791–802.

ICALP-2005-GentryR #communication #constant #information retrieval

Single-Database Private Information Retrieval with Constant Communication Rate (CG, ZR), pp. 803–815.

ICALP-2005-CrescenzoV #concurrent

Concurrent Zero Knowledge in the Public-Key Model (GDC, IV), pp. 816–827.

ICALP-2005-GairingMW #algorithm #approximate #combinator #parallel #performance #scheduling

A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines (MG, BM, AW), pp. 828–839.

ICALP-2005-Kovacs #multi #polynomial

Polynomial Time Preemptive Sum-Multicoloring on Paths (AK), pp. 840–852.

ICALP-2005-JainHT #concurrent #problem

The Generalized Deadlock Resolution Problem (KJ, MTH, KT), pp. 853–865.

ICALP-2005-BadoiuCIS #sublinear

Facility Location in Sublinear Time (MB, AC, PI, CS), pp. 866–877.

ICALP-2005-ChatterjeeAH #complexity #game studies #probability

The Complexity of Stochastic Rabin and Streett Games (KC, LdA, TAH), pp. 878–890.

ICALP-2005-EtessamiY #game studies #markov #probability #process #recursion

Recursive Markov Decision Processes and Recursive Stochastic Games (KE, MY), pp. 891–903.

ICALP-2005-Laird #decidability

Decidability in Syntactic Control of Interference (JL), pp. 904–916.

ICALP-2005-MurawskiOW #algol #equivalence #recursion

Idealized Algol with Ground Recursion, and DPDA Equivalence (ASM, CHLO, IW), pp. 917–929.

ICALP-2005-KonemannLSZ #problem

From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem (JK, SL, GS, SHMvZ), pp. 930–942.

ICALP-2005-BorodinCM #algorithm #how #question

How Well Can Primal-Dual and Local-Ratio Algorithms Perform? (AB, DC, AM), pp. 943–955.

ICALP-2005-Hast #approximate #linear #named #random

Approximating — Outperforming a Random Assignment with Almost a Linear Factor (GH), pp. 956–968.

ICALP-2005-PatrascuP #complexity #on the

On Dynamic Bit-Probe Complexity (CEP, MP), pp. 969–981.

ICALP-2005-DiehlM #bound #polynomial #random

Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines (SD, DvM), pp. 982–993.

ICALP-2005-ChattopadhyayH #bound #composition #symmetry

Lower Bounds for Circuits with Few Modular and Symmetric Gates (AC, KAH), pp. 994–1005.

ICALP-2005-Mislove #random

Discrete Random Variables over Domains (MWM), pp. 1006–1017.

ICALP-2005-BreugelHMW #approach #behaviour #pseudo

An Accessible Approach to Behavioural Pseudometrics (FvB, CH, MM, JW), pp. 1018–1030.

ICALP-2005-AsarinC #turing machine

Noisy Turing Machines (EA, PC), pp. 1031–1042.

ICALP-2005-Karakostas #approximate #problem

A Better Approximation Ratio for the Vertex Cover Problem (GK), pp. 1043–1050.

ICALP-2005-GuptaP #probability

Stochastic Steiner Trees Without a Root (AG, MP), pp. 1051–1063.

ICALP-2005-PemmarajuR #algorithm #approximate #problem

Approximation Algorithms for the Max-coloring Problem (SVP, RR), pp. 1064–1075.

ICALP-2005-GroheKS #bound #memory management #query #streaming

Tight Lower Bounds for Query Processing on Streaming and External Memory Data (MG, CK, NS), pp. 1076–1088.

ICALP-2005-AbdullaDOW #automaton #complexity #decidability

Decidability and Complexity Results for Timed Automata via Channel Machines (PAA, JD, JO, JW), pp. 1089–1101.

ICALP-2005-AlurKMV #automaton

Congruences for Visibly Pushdown Languages (RA, VK, PM, MV), pp. 1102–1114.

ICALP-2005-ElbassioniFMS #algorithm #approximate

Approximation Algorithms for Euclidean Group TSP (KME, AVF, NHM, RS), pp. 1115–1126.

ICALP-2005-KempeKT #network #social

Influential Nodes in a Diffusion Model for Social Networks (DK, JMK, ÉT), pp. 1127–1138.

ICALP-2005-Ambuhl #algorithm #bound #energy #network #performance

An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks (CA), pp. 1139–1150.

ICALP-2005-EisenbrandGOS #design #network

New Approaches for Virtual Private Network Design (FE, FG, GO, MS), pp. 1151–1162.

ICALP-2005-FordG #bound #communication #complexity #multi

Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity (JF, AG), pp. 1163–1175.

ICALP-2005-BeamePS #bound #communication #complexity #multi

Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity (PB, TP, NS), pp. 1176–1188.

ICALP-2005-Wikstrom #integer #on the

On the l-Ary GCD-Algorithm in Rings of Integers (DW), pp. 1189–1201.

ICALP-2005-BaldamusPV #encoding #π-calculus

A Fully Abstract Encoding of the π-Calculus with Data Terms (MB, JP, BV), pp. 1202–1213.

ICALP-2005-MousaviR #orthogonal #semantics

Orthogonal Extensions in Structural Operational Semantics (MRM, MAR), pp. 1214–1225.

ICALP-2005-NicolaGP #calculus

Basic Observables for a Calculus for Global Computing (RDN, DG, RP), pp. 1226–1238.

ICALP-2005-DelzannoG #composition #constraints #process #theorem proving #verification

Compositional Verification of Asynchronous Processes via Constraint Solving (GD, MG), pp. 1239–1250.

ICALP-2005-Farach-ColtonLST #approximate #performance #string

Optimal Spaced Seeds for Faster Approximate String Matching (MFC, GML, SCS, DT), pp. 1251–1262.

ICALP-2005-EliasL #performance

Fast Neighbor Joining (IE, JL), pp. 1263–1274.

ICALP-2005-KaoSS #design #performance #random #word

Randomized Fast Design of Short DNA Words (MYK, MS, RTS), pp. 1275–1286.

ICALP-2005-KoiranNP #bound #complexity #problem #quantum #query

A Quantum Lower Bound for the Query Complexity of Simon’s Problem (PK, VN, NP), pp. 1287–1298.

ICALP-2005-SpalekS #quantum

All Quantum Adversary Methods Are Equivalent (RS, MS), pp. 1299–1311.

ICALP-2005-MagniezN #commutative #complexity #quantum #testing

Quantum Complexity of Testing Group Commutativity (FM, AN), pp. 1312–1324.

ICALP-2005-PredaG #abstract interpretation #obfuscation #semantics

Semantic-Based Code Obfuscation by Abstract Interpretation (MDP, RG), pp. 1325–1336.

ICALP-2005-ReusS #higher-order #hoare #logic

About Hoare Logics for Higher-Order Store (BR, TS), pp. 1337–1348.

ICALP-2005-BradleyMS #principle #ranking

The Polyranking Principle (ARB, ZM, HBS), pp. 1349–1361.

ICALP-2005-Nilsson #approximate

Approximate Guarding of Monotone and Rectilinear Polygons (BJN), pp. 1362–1373.

ICALP-2005-KumarSS #algorithm #clustering #linear #problem

Linear Time Algorithms for Clustering Problems in Any Dimensions (AK, YS, SS), pp. 1374–1385.

ICALP-2005-BerenbrinkFM

Dynamic Diffusion Load Balancing (PB, TF, RAM), pp. 1386–1398.

ICALP-2005-RadhakrishnanRS #fourier #on the #power of #problem #random

On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group (JR, MR, PS), pp. 1399–1411.

ICALP-2005-CaryRS #finite #metric #on the

On the Hardness of Embeddings Between Two Finite Metrics (MC, AR, AS), pp. 1412–1423.

ICALP-2005-WehnerW #bound #information retrieval

Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval (SW, RdW), pp. 1424–1436.

ICALP-2005-AtseriasDG #finite

Preservation Under Extensions on Well-Behaved Finite Structures (AA, AD, MG), pp. 1437–1449.

ICALP-2005-KnapikNUW #automaton

Unsafe Grammars and Panic Automata (TK, DN, PU, IW), pp. 1450–1461.

ICALP-2005-LiDIY #problem #verification

Signaling P Systems and Verification Problems (CL, ZD, OHI, HCY), pp. 1462–1473.