38. ICALP 2011: Zurich, Switzerland - Part I

Luca Aceto, Monika Henzinger, Jiri Sgall (Eds.): Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. Lecture Notes in Computer Science 6755 Springer 2011, ISBN 978-3-642-22005-0

Network Design Problems

Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Improved Approximation for the Directed Spanner Problem. 1-12
Bundit Laekhanukit:
An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity - (Extended Abstract). 13-24
Anna Adamaszek, Artur Czumaj, Andrzej Lingas, Jakub Onufry Wojtaszczyk:
Approximation Schemes for Capacitated Geometric Network Design. 25-36
Jiawei Qian, David P. Williamson:
An O(logn)-Competitive Algorithm for Online Constrained Forest Problems. 37-48

Quantum Computing

Shengyu Zhang:
On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity. 49-60
Scott Aaronson, Andrew Drucker:
Advice Coins for Classical and Quantum Computation. 61-72
André Chailloux, Iordanis Kerenidis, Bill Rosgen:
Quantum Commitments from Complexity Assumptions. 73-85
Aram Wettroth Harrow, Ashley Montanaro, Anthony J. Short:
Limitations on Quantum Dimensionality Reduction. 86-97

Graph Algorithms

Stefan Canzar, Khaled M. Elbassioni, Gunnar W. Klau, Julián Mestre:
On Tree-Constrained Matchings and Generalizations. 98-109
Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos:
Tight Bounds for Linkages in Planar Graphs. 110-121
Markus Chimani, Petr Hlinený:
A Tighter Insertion-Based Approximation of the Crossing Number. 122-134
Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer:
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs. 135-146

Games, Approximation Schemes, Smoothed Analysis

Endre Boros, Khaled M. Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino, Bodo Manthey:
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes. 147-158
Martin E. Dyer, Velumailum Mohanaraj:
Pairwise-Interaction Games. 159-170
Robert Elsässer, Tobias Tscheuschner:
Settling the Complexity of Local Max-Cut (Almost) Completely. 171-182
Tim Nonner:
Clique Clustering Yields a PTAS for max-Coloring Interval Graphs. 183-194

Online Algorithms

Leah Epstein, Csanád Imreh, Asaf Levin, Judit Nagy-György:
On Variants of File Caching. 195-206
Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královic, Richard Královic:
On the Advice Complexity of the k-Server Problem. 207-218
Sze-Hang Chan, Tak Wah Lam, Lap-Kei Lee, Chi-Man Liu, Hing-Fung Ting:
Sleep Management on Multiple Machines for Energy and Flow Time. 219-231
S. Anand, Naveen Garg, Nicole Megow:
Meeting Deadlines: How Much Speed Suffices? 232-243

Data Structures, Distributed Computing

Stephane Durocher, Meng He, J. Ian Munro, Patrick K. Nicholson, Matthew Skala:
Range Majority in Constant Time and Linear Space. 244-255
Gerth Stølting Brodal, Konstantinos Tsakalidis:
Dynamic Planar Range Maxima Queries. 256-267
Arash Farzan, Shahin Kamali:
Compact Navigation and Distance Oracles for Graphs with Small Treewidth. 268-280
Martin Hirt, Vassilis Zikas:
Player-Centric Byzantine Agreement. 281-292

Complexity, Randomness

Eric Allender, Luke Friedman, William I. Gasarch:
Limits on the Computational Power of Random Strings. 293-304
Amin Coja-Oghlan, Angelica Y. Pachon-Pinzon:
The Decimation Process in Random k-SAT. 305-316
Frédéric Magniez, Ashwin Nayak, Miklos Santha, David Xiao:
Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority. 317-329
Ryan O'Donnell, John Wright, Yuan Zhou:
The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions. 330-341

Submodular Optimization, Matroids

Moran Feldman, Joseph Naor, Roy Schwartz:
Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract). 342-353
Chandra Chekuri, Alina Ene:
Submodular Cost Allocation Problem and Applications. 354-366
Naonori Kakimura, Kazuhisa Makino:
Robust Independence Systems. 367-378
Ashwinkumar Badanidiyuru Varadaraja:
Buyback Problem - Approximate Matroid Intersection with Cancellation Costs. 379-390

Cryptography, Learning

Sebastian Faust, Krzysztof Pietrzak, Daniele Venturi:
Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience. 391-402
Sanjeev Arora, Rong Ge:
New Algorithms for Learning in Presence of Errors. 403-415
Ryan C. Harkins, John M. Hitchcock:
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. 416-423

Fixed Parameter Tractability

Andrei A. Bulatov, Dániel Marx:
Constraint Satisfaction Parameterized by Solution Size. 424-436
Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch:
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. 437-448
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk:
Subset Feedback Vertex Set Is Fixed-Parameter Tractable. 449-461
Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard J. Woeginger:
Domination When the Stars Are Out. 462-473

Hardness of Approximation

Per Austrin, Subhash Khot:
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem. 474-485
Uriel Feige, Daniel Reichman:
Recoverable Values for Independent Sets. 486-497
Fabian Kuhn, Monaldo Mastrolilli:
Vertex Cover in Graphs with Locally Few Colors. 498-509
Konstantin Makarychev, Maxim Sviridenko:
Maximizing Polynomials Subject to Assignment Constraints. 510-520

Counting, Testing

Leslie Ann Goldberg, Mark Jerrum:
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. 521-532
Magnus Bordewich, Ross J. Kang:
Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width. 533-544
Sourav Chakraborty, David García-Soriano, Arie Matsliah:
Efficient Sample Extractors for Juntas with Applications. 545-556
Hung Q. Ngo, Ely Porat, Atri Rudra:
Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications - (Extended Abstract). 557-568

Complexity

Lance Fortnow, Rahul Santhanam:
Robust Simulations and Significant Separations. 569-580
Andrew Drucker:
A PCP Characterization of AM. 581-592
Raphaël Clifford, Markus Jalsenius:
Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model. 593-604

Proof Complexity

Lei Huang, Toniann Pitassi:
Automatizability and Simple Stochastic Games. 605-617
Yuval Filmus, Toniann Pitassi, Rahul Santhanam:
Exponential Lower Bounds for AC⁰-Frege Imply Superpolynomial Frege Lower Bounds. 618-629
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov:
Parameterized Bounded-Depth Frege Is Not Optimal. 630-641
Jakob Nordström, Alexander A. Razborov:
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. 642-653

Sorting, Matchings, Paths

Laurent Bulteau, Guillaume Fertin, Irena Rusu:
Sorting by Transpositions Is Difficult. 654-665
Chien-Chung Huang, Telikepalli Kavitha:
Popular Matchings in the Stable Marriage Problem. 666-677
Christine T. Cheng, Eric McDermid, Ichiro Suzuki:
Center Stable Matchings and Centers of Cover Graphs of Distributive Lattices. 678-689
Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, Renato Fonseca F. Werneck:
VC-Dimension and Shortest Path Algorithms. 690-699

Constraint Satisfaction, Algebraic Complexity

Stefan Mengel:
Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems - (Extended Abstract). 700-711
Heng Guo, Pinyan Lu, Leslie G. Valiant:
The Complexity of Symmetric Boolean Parity Holant Problems - (Extended Abstract). 712-723
Maurice J. Jansen, Rahul Santhanam:
Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. 724-735
Eric Allender, Fengming Wang:
On the Power of Algebraic Branching Programs of Width Two. 736-747

Steiner Problems, Clustering

Carsten Moldenhauer:
Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs. 748-759
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner Transitive-Closure Spanners of Low-Dimensional Posets. 760-772
Hu Ding, Jinhui Xu:
Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere. 773-784
Daniel Lokshtanov, Dániel Marx:
Clustering with Local Restrictions. 785-797

Last update Sun May 26 02:11:31 2013 CET by the DBLP Team —

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