37. ICALP 2010: Bordeaux, France - Part I

Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, Paul G. Spirakis (Eds.): Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I. Lecture Notes in Computer Science 6198 Springer 2010, ISBN 978-3-642-14164-5

Invited Talks

Burkhard Monien, Dominic Dumrauf, Tobias Tscheuschner:
Local Search: Simple, Successful, But Sometimes Sluggish. 1-17
Emo Welzl:
When Conflicting Constraints Can Be Resolved - The Lovász Local Lemma and Satisfiability. 18

Session 1-Track A. Combinatorial Optimization

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perkovic:
Plane Spanners of Maximum Degree Six. 19-30
Jop Briët, Fernando Mário de Oliveira Filho, Frank Vallentin:
The Positive Semidefinite Grothendieck Problem with Rank Constraint. 31-42
Amihood Amir, Estrella Eisenberg, Avivit Levy, Ely Porat, Natalie Shapira:
Cycle Detection and Correction. 43-54
Daniel Král':
Decomposition Width of Matroids. 55-66

Session 2-Track A1. Game Theory

MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Nicole Immorlica, Hamid Mahini:
The Cooperative Game Theory Foundations of Network Bargaining Games. 67-78
Tobias Harks, Max Klimm:
On the Existence of Pure Nash Equilibria in Weighted Congestion Games. 79-89
Allan Borodin, Brendan Lucier:
On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions. 90-101
Albert Atserias, Elitza N. Maneva:
Mean-Payoff Games and Propositional Proofs. 102-113

Session 2-Track A2. Security

Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski:
Online Network Design with Outliers. 114-126
Benoît Libert, Moti Yung:
Efficient Completely Non-malleable Public Key Encryption. 127-139
Tsuyoshi Ito:
Polynomial-Space Approximation of No-Signaling Provers. 140-151
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
From Secrecy to Soundness: Efficient Verification via Secure Computation. 152-163

Session 3-Track A1. Data Structures

John Iacono, Özgür Özkan:
Mergeable Dictionaries. 164-175
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai:
Faster Algorithms for Semi-matching Problems (Extended Abstract). 176-187
Jian Li, Ke Yi, Qin Zhang:
Clustering with Diversity. 188-200
Ran Duan:
New Data Structures for Subgraph Connectivity. 201-212

Session 3-Track A2. Sorting & Hashing

Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink:
Tight Thresholds for Cuckoo Hashing via XORSAT. 213-225
Richard Cole, Vijaya Ramachandran:
Resource Oblivious Sorting on Multicores. 226-237
Rosa M. Jiménez, Conrado Martínez:
Interval Sorting. 238-249

Session 4-Track A. Graphs, Nets and Optimization

Nikhil Bansal, Subhash Khot:
Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems. 250-261
Anupam Gupta, Viswanath Nagarajan, R. Ravi:
Thresholded Covering Algorithms for Robust and Max-min Optimization. 262-274
Jin-yi Cai, Xi Chen, Pinyan Lu:
Graph Homomorphisms with Complex Values: A Dichotomy Theorem. 275-286
Nikhil Bansal, Niv Buchbinder, Joseph Naor:
Metrical Task Systems and the k-Server Problem on HSTs. 287-298

Session 5-Track A1. Scheduling

Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, José Verschae, Andreas Wiese:
Scheduling Periodic Tasks in a Hard Real-Time Environment. 299-311
Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs:
Scalably Scheduling Power-Heterogeneous Processors. 312-323
Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan:
Better Scalable Algorithms for Broadcast Scheduling. 324-335
Leah Epstein, Asaf Levin, Rob van Stee:
Max-min Online Allocations with a Reordering Buffer. 336-347

Session 5-Track A2. Graphs & Hypergraphs

Nikolaos Fountoulakis, Konstantinos Panagiotou:
Orientability of Random Hypergraphs and the Power of Multiple Choices. 348-359
Venkatesan Guruswami, Rishi Saket:
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs. 360-371
Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos:
Dynamic Programming for Graphs on Surfaces. 372-383
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky:
Interval Graphs: Canonical Representation in Logspace. 384-395

Session 6-Track A. Best Paper Award

Leslie Ann Goldberg, Mark Jerrum:
Approximating the Partition Function of the Ferromagnetic Potts Model. 396-407

Session 7-Track A. Algebraic Problems

Amir Shpilka, Ilya Volkovich:
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. 408-419
Bruce E. Litow:
On Sums of Roots of Unity. 420-425
Holger Dell, Thore Husfeldt, Martin Wahlen:
Exponential Time Complexity of the Permanent and the Tutte Polynomial. 426-437
Amitava Bhattacharya, Bhaskar DasGupta, Dhruv Mubayi, György Turán:
On Approximate Horn Formula Minimization. 438-450

Session 8-Track A. Networks & Communication Complexity

Amos Beimel, Sebastian Ben Daniel, Eyal Kushilevitz, Enav Weinreb:
Choosing, Agreeing, and Eliminating in Communication Complexity. 451-462
David P. Woodruff:
Additive Spanners in Nearly Quadratic Time. 463-474
Troy Lee, Shengyu Zhang:
Composition Theorems in Communication Complexity. 475-489
Fabrizio Grandoni, Thomas Rothvoß:
Network Design via Core Detouring for Problems without a Core. 490-502

Session 9-Track A1. Complexity & Automata

Klaus Ambos-Spies, Timur Bakibayev:
Weak Completeness Notions for Exponential Time. 503-514
Mikolaj Bojanczyk, Pawel Parys:
Efficient Evaluation of Nondeterministic Automata Using Factorization Forests. 515-526
Tobias Jacobs, Ferdinando Cicalese, Eduardo Sany Laber, Marco Molinaro:
On the Complexity of Searching in Trees: Average-Case Minimization. 527-539

Session 9-Track A2. Finding & Testing

Hari Krovi, Frédéric Magniez, Maris Ozols, Jérémie Roland:
Finding Is as Easy as Detecting for Quantum Walks. 540-551
Mahdi Cheraghchi:
Improved Constructions for Non-adaptive Threshold Group Testing. 552-564
Ronitt Rubinfeld, Ning Xie:
Testing Non-uniform k-Wise Independent Distributions over Product Spaces. 565-581

Session 10-Track A1. Approximations

Iftah Gamzu, Danny Segev:
A Sublogarithmic Approximation for Highway and Tollbooth Pricing. 582-593
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko:
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm. 594-604
Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen, Jakob Truelsen:
Cell Probe Lower Bounds and Approximations for Range Mode. 605-616
Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu:
SDP Gaps for 2-to-1 and Other Label-Cover Variants. 617-628

Session 10-Track A2. Streaming & Preprocessing

Atri Rudra, Steve Uurtamo:
Data Stream Algorithms for Codeword Testing. 629-640
Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy:
Streaming Algorithms for Independent Sets. 641-652
Stefan Kratsch, Magnus Wahlström:
Preprocessing of Min Ones Problems: A Dichotomy. 653-665
Mingji Xia:
Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems. 666-677

Session 11-Track A1. Adaptive, Knowledge & Optimality

Roberto Grossi, Alessio Orlandi, Rajeev Raman:
Optimal Trade-Offs for Succinct String Indexes. 678-689
Anupam Gupta, Viswanath Nagarajan, R. Ravi:
Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems. 690-701
Andrew Chi-Chih Yao, Moti Yung, Yunlei Zhao:
Concurrent Knowledge Extraction in the Public-Key Model. 702-714

Session 11-Track A2. Covering, Graphs & Independence

Mihai Patrascu, Mikkel Thorup:
On the k-Independence Required by Linear Probing and Minwise Independence. 715-726
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto:
Covering and Packing in Linear Space. 727-737
Loukas Georgiadis:
Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs. 738-749

Last update Mon May 20 23:11:09 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page