default search action
38th ICALP 2011: Zurich, Switzerland - Part I
- Luca Aceto, Monika Henzinger, Jirí Sgall
:
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
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 W. Harrow
Limitations on Quantum Dimensionality Reduction. 86-97
Graph Algorithms
- Stefan Canzar
On Tree-Constrained Matchings and Generalizations. 98-109 - Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause
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
Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes. 147-158 - Martin E. Dyer
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
On Variants of File Caching. 195-206 - Hans-Joachim Böckenhauer
On the Advice Complexity of the k-Server Problem. 207-218 - Sze-Hang Chan, Tak Wah Lam
Sleep Management on Multiple Machines for Energy and Flow Time. 219-231 - S. Anand, Naveen Garg
Meeting Deadlines: How Much Speed Suffices? 232-243
Data Structures, Distributed Computing
- Stephane Durocher, Meng He
Range Majority in Constant Time and Linear Space. 244-255 - Gerth Stølting Brodal
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, Angélica Y. Pachón-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
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
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. 437-448 - Marek Cygan
Subset Feedback Vertex Set Is Fixed-Parameter Tractable. 449-461 - Danny Hermelin
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
Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width. 533-544 - Sourav Chakraborty, David García-Soriano
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
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 AC0-Frege Imply Superpolynomial Frege Lower Bounds. 618-629 - Olaf Beyersdorff
Parameterized Bounded-Depth Frege Is Not Optimal. 630-641 - Jakob Nordström
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. 642-653
Sorting, Matchings, Paths
- Laurent Bulteau, Guillaume Fertin
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
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
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-11-22 19:32 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: