default search action
39th ICALP 2012: Warwick, UK - Part I
- Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts
, Roger Wattenhofer:
Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I. Lecture Notes in Computer Science 7391, Springer 2012, ISBN 978-3-642-31593-0
Track A - Algorithms, Complexity and Games
- Dimitris Achlioptas, Ricardo Menchaca-Mendez
Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method. 1-12 - Anil Ada, Arkadev Chattopadhyay, Omar Fawzi
The NOF Multiparty Communication Complexity of Composed Functions. 13-24 - Andris Ambainis, Arturs Backurs, Kaspars Balodis
Quantum Strategies Are Better Than Classical in Almost Any XOR Game. 25-37 - Yossi Azar, Iftah Gamzu:
Efficient Submodular Function Maximization under Linear Packing Constraints. 38-50 - László Babai
Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups - (Extended Abstract). 51-62 - Maria-Florina Balcan, Yingyu Liang:
Clustering under Perturbation Resilience. 63-74 - Siddharth Barman, Seeun Umboh
Secretary Problems with Convex Costs. 75-87 - Joshua Baron, Rafail Ostrovsky, Ivan Visconti:
Nearly Simultaneously Resettable Black-Box Zero Knowledge. 88-99 - Bruno Bauwens
Complexity of Complexity and Maximal Plain versus Prefix-Free Kolmogorov Complexity. 100-108 - Aditya Bhaskara, Moses Charikar
On Quadratic Programming with a Ratio Objective. 109-120 - Prosenjit Bose
De-amortizing Binary Search Trees. 121-132 - Karl Bringmann, Konstantinos Panagiotou:
Efficient Sampling Methods for Discrete Distributions. 133-144 - Niv Buchbinder
Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints. 145-156 - Jaroslaw Byrka, Bartosz Rybicki:
Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location. 157-169 - Deeparnab Chakrabarty, Zhiyi Huang:
Testing Coverage Functions. 170-181 - T.-H. Hubert Chan, Mingfei Li, Li Ning:
Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree. 182-193 - Moses Charikar
A Dependent LP-Rounding Approach for the k-Median Problem. 194-205 - Chandra Chekuri, Alina Ene, Ali Vakilian
Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs. 206-217 - Danny Z. Chen, Haitao Wang:
Computing the Visibility Polygon of an Island in a Polygonal Domain. 218-229 - Rajesh Hemant Chitnis
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. 230-241 - Robert Crowston, Mark Jones, Matthias Mnich
Max-Cut Parameterized above the Edwards-Erdős Bound. 242-253 - Marek Cygan
Clique Cover and Graph Separation: New Incompressibility Results. 254-265 - Anindya De, Ilias Diakonikolas, Rocco A. Servedio
The Inverse Shapley Value Problem. 266-277 - Amit Deshpande, Ravindran Kannan, Nikhil Srivastava:
Zero-One Rounding of Singular Vectors. 278-289 - Michael Dinitz, Guy Kortsarz, Ran Raz:
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner. 290-301 - Yuval Emek, Magnús M. Halldórsson
Space-Constrained Interval Selection. 302-313 - Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations. 314-326 - Arash Farzan, J. Ian Munro, Rajeev Raman
Succinct Indices for Range Queries with Applications to Orthogonal Range Maxima. 327-338 - Uriel Feige, Shlomo Jozeph:
Universal Factor Graphs. 339-350 - Michael R. Fellows
Parameterized Approximation via Fidelity Preserving Transformations. 351-362 - Serge Gaspers, Stefan Szeider
Backdoors to Acyclic SAT. 363-374 - Loukas Georgiadis
Dominators, Directed Bipolar Orders, and Independent Spanning Trees. 375-386 - Sevag Gharibian, Julia Kempe
Hardness of Approximation for Quantum Problems. 387-398 - Leslie Ann Goldberg, Mark Jerrum:
The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation). 399-410 - Inge Li Gørtz
Stochastic Vehicle Routing with Recourse. 411-423 - Anupam Gupta, Kevin Lewi:
The Online Metric Matching Problem for Doubling Metrics. 424-435 - Anupam Gupta, Viswanath Nagarajan:
Approximating Sparse Covering Integer Programs Online. 436-448 - Magnús M. Halldórsson
Streaming and Communication Complexity of Clique Approximation. 449-460 - Justin Hsu
Distributed Private Heavy Hitters. 461-472 - Andrew Hughes, Aduri Pavan, Nathan Russell, Alan L. Selman:
A Thirty Year Old Conjecture about Promise Problems. 473-484 - Sungjin Im, Viswanath Nagarajan, Ruben van der Zwaan:
Minimum Latency Submodular Cover. 485-497 - Hiro Ito, Shin-ichi Tanigawa, Yuichi Yoshida:
Constant-Time Algorithms for Sparsity Matroids. 498-509 - Jesper Jansson
CRAM: Compressed Random Access Memory. 510-521 - Stacey Jeffery, Robin Kothari
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. 522-532 - Artur Jez
Faster Fully Compressed Pattern Matching by Recompression. 533-544 - Michael Kapralov, Rina Panigrahy:
NNS Lower Bounds via Metric Expansion for l ∞ and EMD. 545-556 - Shelby Kimmel
Quantum Adversary (Upper) Bound. 557-568 - Philip N. Klein, Dániel Marx:
Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time. 569-580 - Stefan Kratsch, Marcin Pilipczuk
Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. 581-593 - Robert Krauthgamer
Preserving Terminal Distances Using Minors. 594-605 - Bundit Laekhanukit
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. 606-616 - Sophie Laplante, Virginie Lerays, Jérémie Roland
Classical and Quantum Partition Bound and Detector Inefficiency. 617-628 - Reut Levi, Dana Ron
Testing Similar Means. 629-640 - Bingkai Lin, Yijia Chen:
The Parameterized Complexity of k-Edge Induced Subgraphs. 641-652 - Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie:
Converting Online Algorithms to Local Computation Algorithms. 653-664 - Alberto Marchetti-Spaccamela
Assigning Sporadic Tasks to Unrelated Parallel Machines. 665-676 - Dániel Marx:
A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals. 677-688 - Nicole Megow
The Power of Recourse for Online MST and TSP. 689-700 - Marco Molinaro, R. Ravi:
Geometry of Online Packing Linear Programs. 701-713 - Bin Fu, Matthew J. Patitz
Self-assembly with Geometric Tiles. 714-725 - Lukas Polacek, Ola Svensson:
Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation. 726-737 - Michael O. Rabin, Yishay Mansour, S. Muthukrishnan, Moti Yung:
Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions. 738-749 - Daniel Lokshtanov, M. S. Ramanujan:
Parameterized Tractability of Multiway Cut with Parity Constraints. 750-761 - Barna Saha, Samir Khuller:
Set Cover Revisited: Hypergraph Cover with Hard Capacities. 762-773 - Rahul Santhanam, Srikanth Srinivasan:
On the Limits of Sparsification. 774-785 - Jens M. Schmidt
Certifying 3-Connectivity in Linear Time. 786-797 - Yaoyun Shi, Xiaodi Wu:
Epsilon-Net Method for Optimizations over Separable States. 798-809 - Justin Thaler, Jonathan R. Ullman, Salil P. Vadhan:
Faster Algorithms for Privately Releasing Marginals. 810-821 - Kevin P. Costello
Stochastic Matching with Commitment. 822-833 - Elad Verbin, Qin Zhang:
Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance. 834-845 - Anastasios Zouzias:
A Matrix Hyperbolic Cosine Algorithm and Applications. 846-858
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-28 20:18 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: