default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID34th ICALP 2007: Wroclaw, Poland
- Lars Arge, Christian Cachin, Tomasz Jurdzinski, Andrzej Tarlecki:
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
Invited Lectures
- Bernard Chazelle:
Ushering in a New Era of Algorithm Design. 1 - Ivan Damgård:
A "proof-reading" of Some Issues in Cryptography. 2-11 - Fred B. Schneider:
Credentials-Based Authorization: Evaluation and Implementation. 12-14 - Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos:
Subexponential Parameterized Algorithms. 15-27
Session A1
- Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs:
Competitive Algorithms for Due Date Scheduling. 28-39 - George Christodoulou
, Elias Koutsoupias, Annamária Kovács:
Mechanism Design for Fractional Scheduling on Unrelated Machines. 40-52
Session A2
- Rajeev Motwani, Rina Panigrahy, Ying Xu:
Estimating Sum by Weighted Sampling. 53-64 - Johannes Blömer, Stefanie Naewe:
Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima. 65-77
Session A3
- Seth Pettie:
Low Distortion Spanners. 78-89 - André Berger, Michelangelo Grigni:
Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs. 90-101 - Amos Korman:
Labeling Schemes for Vertex Connectivity. 102-109
Session A4
- Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita:
Unbounded-Error One-Way Classical and Quantum Communication Complexity. 110-121 - Ashley Montanaro, Andreas J. Winter:
A Lower Bound on Entanglement-Assisted Quantum Communication Complexity. 122-133 - Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel:
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. 134-145
Session A5
- Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann:
An Optimal Decomposition Algorithm for Tree Edit Distance. 146-157 - Dragan Bosnacki, Edith Elkind, Blaise Genest, Doron A. Peled:
On Commutativity Based Edge Lean Search. 158-170 - Irit Katriel, Claire Kenyon-Mathieu, Eli Upfal:
Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems. 171-182
Session A6
- Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu:
On the Complexity of Hard-Core Set Constructions. 183-194 - Ryan O'Donnell, Karl Wimmer:
Approximation by DNF: Examples and Counterexamples. 195-206 - Peter Bürgisser, Felipe Cucker:
Exotic Quantifiers, Complexity Classes, and Complete Problems. 207-218
Session A7
- Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky, Shakhar Smorodinsky:
Online Conflict-Free Colorings for Hypergraphs. 219-230 - Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, Andrzej Pelc:
Distributed Computing with Advice: Information Sensitivity of Graph Coloring. 231-242
Session C1
- Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca N. Wright:
Private Multiparty Sampling and Approximation of Vector Combinations. 243-254 - Nenad Dedic, Payman Mohassel:
Constant-Round Private Database Queries. 255-266
Session A8
- Benoît Larose, Pascal Tesson:
Universal Algebra and Hardness Results for Constraint Satisfaction Problems. 267-278 - Albert Atserias, Andrei A. Bulatov, Víctor Dalmau:
On the Power of k -Consistency. 279-290 - Nachum Dershowitz, Iddo Tzameret:
Complexity of Propositional Proofs Under a Promise. 291-302
Session C2
- Tal Moran, Moni Naor, Gil Segev:
Deterministic History-Independent Strategies for Storing Information on Write-Once Memories. 303-315 - Aggelos Kiayias, Hong-Sheng Zhou:
Trading Static for Adaptive Security in Universally Composable Zero-Knowledge. 316-327 - Bruce M. Kapron, Lior Malka, Srinivasan Venkatesh:
A Characterization of Non-interactive Instance-Dependent Commitment-Schemes (NIC). 328-339
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 - Noga Alon, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, Saket Saurabh:
Parameterized Algorithms for Directed Maximum Leaf Problems. 352-362 - Martin Grohe, Magdalena Grüber:
Parameterized Approximability of the Disjoint Cycle Problem. 363-374 - Jiong Guo, Rolf Niedermeier:
Linear Problem Kernels for NP-Hard Problems on Planar Graphs. 375-386
Session C3
- Rafail Ostrovsky, Omkant Pandey, Amit Sahai:
Private Locally Decodable Codes. 387-398 - Mihir Bellare, Thomas Ristenpart:
Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms. 399-410 - Mihir Bellare, Chanathip Namprempre, Gregory Neven:
Unrestricted Aggregate Signatures. 411-422 - Nishanth Chandran, Jens Groth, Amit Sahai:
Ring Signatures of Sub-linear Size Without Random Oracles. 423-434
Session A10
- Noga Alon, Shai Gutner:
Balanced Families of Perfect Hash Functions and Their Applications. 435-446 - Ioannis Caragiannis, Michele Flammini, Luca Moscardelli:
An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks. 447-458
Session B1
- Lutz Schröder, Dirk Pattinson:
Modular Algorithms for Heterogeneous Modal Logics. 459-471 - Luke Simon, Ajay Bansal, Ajay Mallya, Gopal Gupta:
Co-Logic Programming: Extending Logic Programming with Coinduction. 472-483
Session C4
- Ben Adida, Douglas Wikström:
Offline/Online Mixing. 484-495 - Jun Furukawa, Nuttapong Attrapadung:
Fully Collusion Resistant Black-Box Traitor Revocable Broadcast Encryption with Short Private Keys. 496-508
Session A11
- Meng He, J. Ian Munro, S. Srinivasa Rao:
Succinct Ordinal Trees Based on Tree Covering. 509-520 - Ankur Gupta, Wing-Kai Hon, Rahul Shah, Jeffrey Scott Vitter:
A Framework for Dynamizing Succinct Data Structures. 521-532 - Gianni Franceschini, S. Muthukrishnan:
In-Place Suffix Sorting. 533-545
Session B2
- Manuel Bodirsky, Hubie Chen, Jan Kára, Timo von Oertzen:
Maximal Infinite-Valued Constraint Languages. 546-557 - Albert Atserias, Andrei A. Bulatov, Anuj Dawar:
Affine Systems of Equations and Counting Infinitary Logic. 558-570 - Stephan Kreutzer, Martin Otto, Nicole Schweikardt:
Boundedness of Monadic FO over Acyclic Structures. 571-582
Session A12
- Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky:
Strong Price of Anarchy for Machine Load Balancing. 583-594 - Spyros C. Kontogiannis, Paul G. Spirakis:
Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games. 595-606
Session B3
- Marcelo P. Fiore, Chung-Kil Hur:
Equational Systems and Free Constructions (Extended Abstract). 607-618 - Ichiro Hasuo, Bart Jacobs, Tarmo Uustalu:
Categorical Views on Computations on Trees (Extended Abstract). 619-630
Session A13
- Jin-yi Cai, Pinyan Lu:
Holographic Algorithms: The Power of Dimensionality Resolved. 631-642 - Laurent Bienvenu, Wolfgang Merkle:
Reconciling Data Compression and Kolmogorov Complexity. 643-654 - Gary L. Miller, Todd Phillips, Donald R. Sheehy:
Size Competitive Meshing Without Large Angles. 655-666
Session B4
- James Laird:
A Fully Abstract Trace Semantics for General References. 667-679 - Jonathan K. Lee, Jens Palsberg, Fernando Magno Quintão Pereira:
Aliased Register Allocation for Straight-Line Programs Is NP-Complete. 680-691 - Sylvain Schmitz:
Conservative Ambiguity Detection in Context-Free Grammars. 692-703
Session A14
- Sudipto Guha, Andrew McGregor:
Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming. 704-715 - Michael Elkin:
Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners. 716-727 - Matthew Chu, Sampath Kannan, Andrew McGregor:
Checking and Spot-Checking the Correctness of Priority Queues. 728-739
Session B5
- Naoki Kobayashi, Takashi Suto:
Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the pi -Calculus. 740-751 - Gerald Lüttgen, Walter Vogler:
Ready Simulation for Concurrency: It's Logical! 752-763 - Jean Goubault-Larrecq:
Continuous Capacities on Continuous State Spaces. 764-776
Session A15
- Amin Coja-Oghlan, Konstantinos Panagiotou, Angelika Steger:
On the Chromatic Number of Random Graphs. 777-788 - 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 - Markus Bläser, Holger Dell:
Complexity of the Cover Polynomial. 801-812
Session B6
- Bernard Boigelot, Julien Brusten:
A Generalization of Cobham's Theorem to Automata over Real Numbers. 813-824 - Thomas Brihaye, Thomas A. Henzinger, Vinayak S. Prabhu, Jean-François Raskin:
Minimum-Time Reachability in Timed Games. 825-837 - Marcin Jurdzinski, Ashutosh Trivedi:
Reachability-Time Games on Timed Automata. 838-849 - Hugo Gimbert, Wieslaw Zielonka:
Perfect Information Stochastic Priority Games. 850-861
Session B7
- Henrik Björklund, Mikolaj Bojanczyk:
Bounded Depth Data Trees. 862-874 - Karianto Wong, Christof Löding:
Unranked Tree Automata with Sibling Equalities and Disequalities. 875-887 - Marcelo Arenas, Pablo Barceló, Leonid Libkin:
Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization. 888-900 - Thomas Colcombet:
A Combinatorial Theorem for Trees. 901-912
Session B8
- Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt:
Model Theory Makes Formulas Large. 913-924 - Laura Bozzelli, Salvatore La Torre:
Decision Problems for Lower/Upper Bound Parametric Timed Automata. 925-936 - Salvatore La Torre, Gennaro Parlato:
On the Complexity of LtlModel-Checking of Recursive State Machines. 937-948
Paper Retraction
- Matthew Cary, Atri Rudra, Ashish Sabharwal:
Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics. 949
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-10-31 20:20 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:
