Lars Arge, Christian Cachin, Tomasz Jurdzinski, Andrzej Tarlecki
Proceedings of the 34th International Colloquium on Automata, Languages and Programming
ICALP, 2007.

@proceedings{ICALP-2007,
	address       = "Wroclaw, Poland",
	editor        = "Lars Arge and Christian Cachin and Tomasz Jurdzinski and Andrzej Tarlecki",
	isbn          = "978-3-540-73419-2",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 34th International Colloquium on Automata, Languages and Programming}",
	volume        = 4596,
	year          = 2007,
}

Contents (81 items)

10 ×#algorithm
9 ×#complexity
7 ×#problem
6 ×#bound
6 ×#graph
5 ×#automaton
5 ×#on the
4 ×#game studies
3 ×#approximate
3 ×#communication

ICALP-2007-Chazelle #algorithm #design

Ushering in a New Era of Algorithm Design (BC), p. 1.

ICALP-2007-Damgard #encryption

A “proof-reading” of Some Issues in Cryptography (ID), pp. 2–11.

ICALP-2007-Schneider #evaluation #implementation

Credentials-Based Authorization: Evaluation and Implementation (FBS), pp. 12–14.

ICALP-2007-DornFT #algorithm

Subexponential Parameterized Algorithms (FD, FVF, DMT), pp. 15–27.

ICALP-2007-BansalCP #algorithm #scheduling

Competitive Algorithms for Due Date Scheduling (NB, HLC, KP), pp. 28–39.

ICALP-2007-ChristodoulouKK #design #scheduling

Mechanism Design for Fractional Scheduling on Unrelated Machines (GC, EK, AK), pp. 40–52.

ICALP-2007-MotwaniPX

Estimating Sum by Weighted Sampling (RM, RP, YX), pp. 53–64.

ICALP-2007-BlomerN

Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima (JB, SN), pp. 65–77.

ICALP-2007-Pettie

Low Distortion Spanners (SP), pp. 78–89.

ICALP-2007-BergerG #graph

Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs (AB, MG), pp. 90–101.

ICALP-2007-Korman

Labeling Schemes for Vertex Connectivity (AK), pp. 102–109.

ICALP-2007-IwamaNRY #bound #communication #complexity #quantum

Unbounded-Error One-Way Classical and Quantum Communication Complexity (KI, HN, RR, SY), pp. 110–121.

ICALP-2007-MontanaroW #bound #communication #complexity #quantum

A Lower Bound on Entanglement-Assisted Quantum Communication Complexity (AM, AJW), pp. 122–133.

ICALP-2007-BeameDPW #communication #complexity #multi #nondeterminism

Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity (PB, MD, TP, PW), pp. 134–145.

ICALP-2007-DemaineMRW #algorithm #composition #distance #edit distance

An Optimal Decomposition Algorithm for Tree Edit Distance (EDD, SM, BR, OW), pp. 146–157.

ICALP-2007-BosnackiEGP #agile #commutative #on the

On Commutativity Based Edge Lean Search (DB, EE, BG, DP), pp. 158–170.

ICALP-2007-KatrielKU #nondeterminism #probability #problem

Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems (IK, CKM, EU), pp. 171–182.

ICALP-2007-LuTW #complexity #on the #set

On the Complexity of Hard-Core Set Constructions (CJL, SCT, HLW), pp. 183–194.

ICALP-2007-ODonnellW #approximate

Approximation by DNF: Examples and Counterexamples (RO, KW), pp. 195–206.

ICALP-2007-BurgisserC #complexity #problem #quantifier

Exotic Quantifiers, Complexity Classes, and Complete Problems (PB, FC), pp. 207–218.

ICALP-2007-Bar-NoyCOS #online

Online Conflict-Free Colorings for Hypergraphs (ABN, PC, SO, SS), pp. 219–230.

ICALP-2007-FraigniaudGIP #distributed #graph

Distributed Computing with Advice: Information Sensitivity of Graph Coloring (PF, CG, DI, AP), pp. 231–242.

ICALP-2007-IshaiMSW #approximate #multi

Private Multiparty Sampling and Approximation of Vector Combinations (YI, TM, MJS, RNW), pp. 243–254.

ICALP-2007-DedicM #database #query

Constant-Round Private Database Queries (ND, PM), pp. 255–266.

ICALP-2007-LaroseT #algebra #constraints #problem

Universal Algebra and Hardness Results for Constraint Satisfaction Problems (BL, PT), pp. 267–278.

ICALP-2007-AtseriasBD #on the #power of

On the Power of k -Consistency (AA, AAB, VD), pp. 279–290.

ICALP-2007-DershowitzT #complexity #proving

Complexity of Propositional Proofs Under a Promise (ND, IT), pp. 291–302.

ICALP-2007-MoranNS #independence #information management

Deterministic History-Independent Strategies for Storing Information on Write-Once Memories (TM, MN, GS), pp. 303–315.

ICALP-2007-KiayiasZ #adaptation #composition #security

Trading Static for Adaptive Security in Universally Composable Zero-Knowledge (AK, HSZ), pp. 316–327.

ICALP-2007-KapronMS

A Characterization of Non-interactive Instance-Dependent Commitment-Schemes (NIC) (BMK, LM, SV), pp. 328–339.

ICALP-2007-FellowsFHV #graph

Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs (MRF, GF, DH, SV), pp. 340–351.

ICALP-2007-AlonFGKS #algorithm #problem

Parameterized Algorithms for Directed Maximum Leaf Problems (NA, FVF, GG, MK, SS), pp. 352–362.

ICALP-2007-GroheG #problem

Parameterized Approximability of the Disjoint Cycle Problem (MG, MG), pp. 363–374.

ICALP-2007-GuoN #graph #kernel #linear #np-hard #problem

Linear Problem Kernels for NP-Hard Problems on Planar Graphs (JG, RN), pp. 375–386.

ICALP-2007-OstrovskyPS

Private Locally Decodable Codes (RO, OP, AS), pp. 387–398.

ICALP-2007-BellareR #design

Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms (MB, TR), pp. 399–410.

ICALP-2007-BellareNN #strict

Unrestricted Aggregate Signatures (MB, CN, GN), pp. 411–422.

ICALP-2007-ChandranGS #random

Ring Signatures of Sub-linear Size Without Random Oracles (NC, JG, AS), pp. 423–434.

ICALP-2007-AlonG #product line

Balanced Families of Perfect Hash Functions and Their Applications (NA, SG), pp. 435–446.

ICALP-2007-CaragiannisFM #ad hoc #energy #exponential #heuristic #network

An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks (IC, MF, LM), pp. 447–458.

ICALP-2007-SchroderP #algorithm #composition #logic

Modular Algorithms for Heterogeneous Modal Logics (LS, DP), pp. 459–471.

ICALP-2007-SimonBMG #induction #logic programming

Co-Logic Programming: Extending Logic Programming with Coinduction (LS, AB, AM, GG), pp. 472–483.

ICALP-2007-AdidaW #online

Offline/Online Mixing (BA, DW), pp. 484–495.

ICALP-2007-FurukawaA #black box #encryption

Fully Collusion Resistant Black-Box Traitor Revocable Broadcast Encryption with Short Private Keys (JF, NA), pp. 496–508.

ICALP-2007-HeMR

Succinct Ordinal Trees Based on Tree Covering (MH, JIM, SSR), pp. 509–520.

ICALP-2007-GuptaHSV #data type #framework

A Framework for Dynamizing Succinct Data Structures (AG, WKH, RS, JSV), pp. 521–532.

ICALP-2007-FranceschiniM #sorting

In-Place Suffix Sorting (GF, SM), pp. 533–545.

ICALP-2007-BodirskyCKO #constraints

Maximal Infinite-Valued Constraint Languages (MB, HC, JK, TvO), pp. 546–557.

ICALP-2007-AtseriasBD07a #equation #logic

Affine Systems of Equations and Counting Infinitary Logic (AA, AAB, AD), pp. 558–570.

ICALP-2007-KreutzerOS #bound #monad

Boundedness of Monadic FO over Acyclic Structures (SK, MO, NS), pp. 571–582.

ICALP-2007-FiatKLO

Strong Price of Anarchy for Machine Load Balancing (AF, HK, ML, SO), pp. 583–594.

ICALP-2007-KontogiannisS #algorithm #approximate #constant #game studies #performance

Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games (SCK, PGS), pp. 595–606.

ICALP-2007-FioreH #equation

Equational Systems and Free Constructions (MPF, CKH), pp. 607–618.

ICALP-2007-HasuoJU #category theory

Categorical Views on Computations on Trees (IH, BJ, TU), pp. 619–630.

ICALP-2007-CaiL #algorithm #artificial reality #power of

Holographic Algorithms: The Power of Dimensionality Resolved (JyC, PL), pp. 631–642.

ICALP-2007-BienvenuM #complexity

Reconciling Data Compression and Kolmogorov Complexity (LB, WM), pp. 643–654.

ICALP-2007-MillerPS #scalability

Size Competitive Meshing Without Large Angles (GLM, TP, DS), pp. 655–666.

ICALP-2007-Laird #semantics

A Fully Abstract Trace Semantics for General References (JL), pp. 667–679.

ICALP-2007-LeePP #alias #source code

Aliased Register Allocation for Straight-Line Programs Is NP-Complete (JKL, JP, FMQP), pp. 680–691.

ICALP-2007-Schmitz #ambiguity #context-free grammar #detection

Conservative Ambiguity Detection in Context-Free Grammars (SS), pp. 692–703.

ICALP-2007-GuhaM #bound #estimation #multi #streaming

Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming (SG, AM), pp. 704–715.

ICALP-2007-Elkin #algorithm #maintenance #streaming

Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners (ME), pp. 716–727.

ICALP-2007-ChuKM #correctness

Checking and Spot-Checking the Correctness of Priority Queues (MC, SK, AM), pp. 728–739.

ICALP-2007-KobayashiS #behaviour #calculus #type system

Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the π -Calculus (NK, TS), pp. 740–751.

ICALP-2007-LuttgenV #concurrent #exclamation #logic #simulation

Ready Simulation for Concurrency: It’s Logical! (GL, WV), pp. 752–763.

ICALP-2007-Goubault-Larrecq

Continuous Capacities on Continuous State Spaces (JGL), pp. 764–776.

ICALP-2007-Coja-OghlanPS #graph #on the #random

On the Chromatic Number of Random Graphs (ACO, KP, AS), pp. 777–788.

ICALP-2007-AlonCHKRS #algorithm #graph

Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions (NA, ACO, HH, MK, VR, MS), pp. 789–800.

ICALP-2007-BlaserD #complexity #polynomial

Complexity of the Cover Polynomial (MB, HD), pp. 801–812.

ICALP-2007-BoigelotB #automaton #theorem

A Generalization of Cobham’s Theorem to Automata over Real Numbers (BB, JB), pp. 813–824.

ICALP-2007-BrihayeHPR #game studies #reachability

Minimum-Time Reachability in Timed Games (TB, TAH, VSP, JFR), pp. 825–837.

ICALP-2007-JurdzinskiT #automaton #game studies

Reachability-Time Games on Timed Automata (MJ, AT), pp. 838–849.

ICALP-2007-GimbertZ #game studies #probability

Perfect Information Stochastic Priority Games (HG, WZ), pp. 850–861.

ICALP-2007-BjorklundB #bound

Bounded Depth Data Trees (HB, MB), pp. 862–874.

ICALP-2007-KariantoL #automaton

Unranked Tree Automata with Sibling Equalities and Disequalities (KW, CL), pp. 875–887.

ICALP-2007-ArenasBL #automaton #fixpoint #regular expression #word

Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization (MA, PB, LL), pp. 888–900.

ICALP-2007-Colcombet #combinator #theorem

A Combinatorial Theorem for Trees (TC), pp. 901–912.

ICALP-2007-DawarGKS #scalability

Model Theory Makes Formulas Large (AD, MG, SK, NS), pp. 913–924.

ICALP-2007-BozzelliT #automaton #bound #parametricity #problem

Decision Problems for Lower/Upper Bound Parametric Timed Automata (LB, SLT), pp. 925–936.

ICALP-2007-TorreP #complexity #model checking #on the #recursion #state machine

On the Complexity of LtlModel-Checking of Recursive State Machines (SLT, GP), pp. 937–948.

ICALP-2007-CaryRS #finite #metric

Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics (MC, AR, AS), p. 949.