34. ICALP 2007: Wroclaw, Poland

Lars Arge, Christian Cachin, Tomasz Jurdzinski, Andrzej Tarlecki (Eds.): Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings. Lecture Notes in Computer Science 4596 Springer 2007, ISBN 978-3-540-73419-2 BibTeX

Invited Lectures

Bernard Chazelle:
Ushering in a New Era of Algorithm Design. 1
Electronic Edition (link) BibTeX
Ivan Damgård:
A "proof-reading" of Some Issues in Cryptography. 2-11
Electronic Edition (link) BibTeX
Fred B. Schneider:
Credentials-Based Authorization: Evaluation and Implementation. 12-14
Electronic Edition (link) BibTeX
Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos:
Subexponential Parameterized Algorithms. 15-27
Electronic Edition (link) BibTeX

Session A1

Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs:
Competitive Algorithms for Due Date Scheduling. 28-39
Electronic Edition (link) BibTeX
George Christodoulou, Elias Koutsoupias, Annamária Kovács:
Mechanism Design for Fractional Scheduling on Unrelated Machines. 40-52
Electronic Edition (link) BibTeX

Session A2

Rajeev Motwani, Rina Panigrahy, Ying Xu:
Estimating Sum by Weighted Sampling. 53-64
Electronic Edition (link) BibTeX
Johannes Blömer, Stefanie Naewe:
Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima. 65-77
Electronic Edition (link) BibTeX

Session A3

Seth Pettie:
Low Distortion Spanners. 78-89
Electronic Edition (link) BibTeX
André Berger, Michelangelo Grigni:
Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs. 90-101
Electronic Edition (link) BibTeX
Amos Korman:
Labeling Schemes for Vertex Connectivity. 102-109
Electronic Edition (link) BibTeX

Session A4

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita:
Unbounded-Error One-Way Classical and Quantum Communication Complexity. 110-121
Electronic Edition (link) BibTeX
Ashley Montanaro, Andreas Winter:
A Lower Bound on Entanglement-Assisted Quantum Communication Complexity. 122-133
Electronic Edition (link) BibTeX
Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel:
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. 134-145
Electronic Edition (link) BibTeX

Session A5

Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann:
An Optimal Decomposition Algorithm for Tree Edit Distance. 146-157
Electronic Edition (link) BibTeX
Dragan Bosnacki, Edith Elkind, Blaise Genest, Doron Peled:
On Commutativity Based Edge Lean Search. 158-170
Electronic Edition (link) BibTeX
Irit Katriel, Claire Kenyon-Mathieu, Eli Upfal:
Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems. 171-182
Electronic Edition (link) BibTeX

Session A6

Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu:
On the Complexity of Hard-Core Set Constructions. 183-194
Electronic Edition (link) BibTeX
Ryan O'Donnell, Karl Wimmer:
Approximation by DNF: Examples and Counterexamples. 195-206
Electronic Edition (link) BibTeX
Peter Bürgisser, Felipe Cucker:
Exotic Quantifiers, Complexity Classes, and Complete Problems. 207-218
Electronic Edition (link) BibTeX

Session A7

Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky:
Online Conflict-Free Colorings for Hypergraphs. 219-230
Electronic Edition (link) BibTeX
Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, Andrzej Pelc:
Distributed Computing with Advice: Information Sensitivity of Graph Coloring. 231-242
Electronic Edition (link) BibTeX

Session C1

Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca N. Wright:
Private Multiparty Sampling and Approximation of Vector Combinations. 243-254
Electronic Edition (link) BibTeX
Nenad Dedic, Payman Mohassel:
Constant-Round Private Database Queries. 255-266
Electronic Edition (link) BibTeX

Session A8

Benoit Larose, Pascal Tesson:
Universal Algebra and Hardness Results for Constraint Satisfaction Problems. 267-278
Electronic Edition (link) BibTeX
Albert Atserias, Andrei A. Bulatov, Víctor Dalmau:
On the Power of k -Consistency. 279-290
Electronic Edition (link) BibTeX
Nachum Dershowitz, Iddo Tzameret:
Complexity of Propositional Proofs Under a Promise. 291-302
Electronic Edition (link) BibTeX

Session C2

Tal Moran, Moni Naor, Gil Segev:
Deterministic History-Independent Strategies for Storing Information on Write-Once Memories. 303-315
Electronic Edition (link) BibTeX
Aggelos Kiayias, Hong-Sheng Zhou:
Trading Static for Adaptive Security in Universally Composable Zero-Knowledge. 316-327
Electronic Edition (link) BibTeX
Bruce M. Kapron, Lior Malka, Srinivasan Venkatesh:
A Characterization of Non-interactive Instance-Dependent Commitment-Schemes (NIC). 328-339
Electronic Edition (link) BibTeX

Session A9

Michael R. Fellows, Guillaume Fertin, Danny Hermelin, Stéphane Vialette:
Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs. 340-351
Electronic Edition (link) BibTeX
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh:
Parameterized Algorithms for Directed Maximum Leaf Problems. 352-362
Electronic Edition (link) BibTeX
Martin Grohe, Magdalena Grüber:
Parameterized Approximability of the Disjoint Cycle Problem. 363-374
Electronic Edition (link) BibTeX
Jiong Guo, Rolf Niedermeier:
Linear Problem Kernels for NP-Hard Problems on Planar Graphs. 375-386
Electronic Edition (link) BibTeX

Session C3

Rafail Ostrovsky, Omkant Pandey, Amit Sahai:
Private Locally Decodable Codes. 387-398
Electronic Edition (link) BibTeX
Mihir Bellare, Thomas Ristenpart:
Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms. 399-410
Electronic Edition (link) BibTeX
Mihir Bellare, Chanathip Namprempre, Gregory Neven:
Unrestricted Aggregate Signatures. 411-422
Electronic Edition (link) BibTeX
Nishanth Chandran, Jens Groth, Amit Sahai:
Ring Signatures of Sub-linear Size Without Random Oracles. 423-434
Electronic Edition (link) BibTeX

Session A10

Noga Alon, Shai Gutner:
Balanced Families of Perfect Hash Functions and Their Applications. 435-446
Electronic Edition (link) BibTeX
Ioannis Caragiannis, Michele Flammini, Luca Moscardelli:
An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks. 447-458
Electronic Edition (link) BibTeX

Session B1

Lutz Schröder, Dirk Pattinson:
Modular Algorithms for Heterogeneous Modal Logics. 459-471
Electronic Edition (link) BibTeX
Luke Simon, Ajay Bansal, Ajay Mallya, Gopal Gupta:
Co-Logic Programming: Extending Logic Programming with Coinduction. 472-483
Electronic Edition (link) BibTeX

Session C4

Ben Adida, Douglas Wikström:
Offline/Online Mixing. 484-495
Electronic Edition (link) BibTeX
Jun Furukawa, Nuttapong Attrapadung:
Fully Collusion Resistant Black-Box Traitor Revocable Broadcast Encryption with Short Private Keys. 496-508
Electronic Edition (link) BibTeX

Session A11

Meng He, J. Ian Munro, S. Srinivasa Rao:
Succinct Ordinal Trees Based on Tree Covering. 509-520
Electronic Edition (link) BibTeX
Ankur Gupta, Wing-Kai Hon, Rahul Shah, Jeffrey Scott Vitter:
A Framework for Dynamizing Succinct Data Structures. 521-532
Electronic Edition (link) BibTeX
Gianni Franceschini, S. Muthukrishnan:
In-Place Suffix Sorting. 533-545
Electronic Edition (link) BibTeX

Session B2

Manuel Bodirsky, Hubie Chen, Jan Kára, Timo von Oertzen:
Maximal Infinite-Valued Constraint Languages. 546-557
Electronic Edition (link) BibTeX
Albert Atserias, Andrei A. Bulatov, Anuj Dawar:
Affine Systems of Equations and Counting Infinitary Logic. 558-570
Electronic Edition (link) BibTeX
Stephan Kreutzer, Martin Otto, Nicole Schweikardt:
Boundedness of Monadic FO over Acyclic Structures. 571-582
Electronic Edition (link) BibTeX

Session A12

Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky:
Strong Price of Anarchy for Machine Load Balancing. 583-594
Electronic Edition (link) BibTeX
Spyros C. Kontogiannis, Paul G. Spirakis:
Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games. 595-606
Electronic Edition (link) BibTeX

Session B3

Marcelo P. Fiore, Chung-Kil Hur:
Equational Systems and Free Constructions (Extended Abstract). 607-618
Electronic Edition (link) BibTeX
Ichiro Hasuo, Bart Jacobs, Tarmo Uustalu:
Categorical Views on Computations on Trees (Extended Abstract). 619-630
Electronic Edition (link) BibTeX

Session A13

Jin-yi Cai, Pinyan Lu:
Holographic Algorithms: The Power of Dimensionality Resolved. 631-642
Electronic Edition (link) BibTeX
Laurent Bienvenu, Wolfgang Merkle:
Reconciling Data Compression and Kolmogorov Complexity. 643-654
Electronic Edition (link) BibTeX
Gary L. Miller, Todd Phillips, Donald Sheehy:
Size Competitive Meshing Without Large Angles. 655-666
Electronic Edition (link) BibTeX

Session B4

James Laird:
A Fully Abstract Trace Semantics for General References. 667-679
Electronic Edition (link) BibTeX
Jonathan K. Lee, Jens Palsberg, Fernando Magno Quintão Pereira:
Aliased Register Allocation for Straight-Line Programs Is NP-Complete. 680-691
Electronic Edition (link) BibTeX
Sylvain Schmitz:
Conservative Ambiguity Detection in Context-Free Grammars. 692-703
Electronic Edition (link) BibTeX

Session A14

Sudipto Guha, Andrew McGregor:
Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming. 704-715
Electronic Edition (link) BibTeX
Michael Elkin:
Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners. 716-727
Electronic Edition (link) BibTeX
Matthew Chu, Sampath Kannan, Andrew McGregor:
Checking and Spot-Checking the Correctness of Priority Queues. 728-739
Electronic Edition (link) BibTeX

Session B5

Naoki Kobayashi, Takashi Suto:
Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the pi -Calculus. 740-751
Electronic Edition (link) BibTeX
Gerald Lüttgen, Walter Vogler:
Ready Simulation for Concurrency: It's Logical! 752-763
Electronic Edition (link) BibTeX
Jean Goubault-Larrecq:
Continuous Capacities on Continuous State Spaces. 764-776
Electronic Edition (link) BibTeX

Session A15

Amin Coja-Oghlan, Konstantinos Panagiotou, Angelika Steger:
On the Chromatic Number of Random Graphs. 777-788
Electronic Edition (link) BibTeX
Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtech Rödl, Mathias Schacht:
Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions. 789-800
Electronic Edition (link) BibTeX
Markus Bläser, Holger Dell:
Complexity of the Cover Polynomial. 801-812
Electronic Edition (link) BibTeX

Session B6

Bernard Boigelot, Julien Brusten:
A Generalization of Cobham's Theorem to Automata over Real Numbers. 813-824
Electronic Edition (link) BibTeX
Thomas Brihaye, Thomas A. Henzinger, Vinayak S. Prabhu, Jean-François Raskin:
Minimum-Time Reachability in Timed Games. 825-837
Electronic Edition (link) BibTeX
Marcin Jurdzinski, Ashutosh Trivedi:
Reachability-Time Games on Timed Automata. 838-849
Electronic Edition (link) BibTeX
Hugo Gimbert, Wieslaw Zielonka:
Perfect Information Stochastic Priority Games. 850-861
Electronic Edition (link) BibTeX

Session B7

Henrik Björklund, Mikolaj Bojanczyk:
Bounded Depth Data Trees. 862-874
Electronic Edition (link) BibTeX
Wong Karianto, Christof Löding:
Unranked Tree Automata with Sibling Equalities and Disequalities. 875-887
Electronic Edition (link) BibTeX
Marcelo Arenas, Pablo Barceló, Leonid Libkin:
Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization. 888-900
Electronic Edition (link) BibTeX
Thomas Colcombet:
A Combinatorial Theorem for Trees. 901-912
Electronic Edition (link) BibTeX

Session B8

Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt:
Model Theory Makes Formulas Large. 913-924
Electronic Edition (link) BibTeX
Laura Bozzelli, Salvatore La Torre:
Decision Problems for Lower/Upper Bound Parametric Timed Automata. 925-936
Electronic Edition (link) BibTeX
Salvatore La Torre, Gennaro Parlato:
On the Complexity of LtlModel-Checking of Recursive State Machines. 937-948
Electronic Edition (link) BibTeX

Paper Retraction

Matthew Cary, Atri Rudra, Ashish Sabharwal:
Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics. 949
Electronic Edition (link) BibTeX