default search action
40th ICALP 2013: Riga, Latvia - Part I
- Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, David Peleg:
Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I. Lecture Notes in Computer Science 7965, Springer 2013, ISBN 978-3-642-39205-4
Track A - Algorithms, Complexity and Games
- Amir Abboud, Kevin Lewi:
Exact Weight Subgraphs and the k-Sum Conjecture. 1-12 - S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg
, Amit Kumar
Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines. 13-24 - Alexandr Andoni, Huy L. Nguyên, Yury Polyanskiy, Yihong Wu:
Tight Lower Bound for Linear Sketches of Moments. 25-32 - Martin Aumüller, Martin Dietzfelbinger:
Optimal Partitioning for Dual Pivot Quicksort - (Extended Abstract). 33-44 - Per Austrin, Petteri Kaski, Mikko Koivisto
Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm. 45-56 - David Avis, Hans Raj Tiwary
On the Extension Complexity of Combinatorial Polytopes. 57-68 - Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan:
Algorithms for Hub Label Optimization. 69-80 - MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Vahid Liaghat:
Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems. 81-92 - Reinhard Bauer, Tobias Columbus, Ignaz Rutter
Search-Space Size in Contraction Hierarchies. 93-104 - Aleksandrs Belovs, Andrew M. Childs
Time-Efficient Quantum Walks for 3-Distinctness. 105-122 - Arnab Bhattacharyya, Yuichi Yoshida:
An Algebraic Characterization of Testable Boolean CSPs. 123-134 - Marcin Bienkowski
Approximation Algorithms for the Joint Replenishment Problem with Deadlines. 135-147 - Philip Bille
Sparse Suffix Tree Construction in Small Space. 148-159 - Philip Bille
Tree Compression with Top Trees. 160-171 - Markus Bläser:
Noncommutativity Makes Determinants Hard. 172-183 - Thomas Bläsius, Ignaz Rutter
Optimal Orthogonal Graph Drawing with Convex Bend Costs. 184-195 - Hans L. Bodlaender
Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth. 196-207 - Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu
On the Complexity of Higher Order Abstract Voronoi Diagrams. 208-219 - Endre Boros, Khaled M. Elbassioni
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions. 220-231 - Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct Product via Round-Preserving Compression. 232-243 - Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik:
How Hard Is Counting Triangles in the Streaming Model? 244-254 - Karl Bringmann, Benjamin Doerr, Adrian Neumann, Jakub Sliacan:
Online Checkpointing with Improved Worst-Case Guarantees. 255-266 - Karl Bringmann, Tobias Friedrich:
Exact and Efficient Generation of Geometric Random Variates and Random Graphs. 267-278 - Tobias Brunsch, Heiko Röglin
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm. 279-290 - Jan Bulánek, Michal Koucký
On Randomized Online Labeling with Polynomially Many Labels. 291-302 - Mark Bun, Justin Thaler:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. 303-314 - T.-H. Hubert Chan, Mingfei Li, Li Ning, Shay Solomon:
New Doubling Spanners: Better and Simpler. 315-327 - Chandra Chekuri, Guyslain Naves, F. Bruce Shepherd:
Maximum Edge-Disjoint Paths in k-Sums of Graphs. 328-339 - Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla:
On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy. 340-351 - Radu Curticapean:
Counting Matchings of Size k Is W[1]-Hard. 352-363 - Marek Cygan
Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree. 364-375 - Anindya De, Ilias Diakonikolas, Rocco A. Servedio
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry. 376-387 - Erik D. Demaine, John Iacono
Combining Binary Search Trees. 388-399 - Erik D. Demaine, Matthew J. Patitz
The Two-Handed Tile Assembly Model Is Not Intrinsically Universal. 400-412 - Irit Dinur
Clustering in the Boolean Hypercube in a List Decoding Regime. 413-424 - Ran Duan, Kurt Mehlhorn:
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. 425-436 - Yuval Filmus, Massimo Lauria
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds - (Extended Abstract). 437-448 - Dimitris Fotakis
On the Power of Deterministic Mechanisms for Facility Location Games. 449-460 - Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, Martin J. Strauss:
ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk. 461-472 - Christian Glaßer, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek:
Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions. 473-484 - Petr A. Golovach
An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. 485-496 - Daniel Grier:
Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete. 497-503 - Roberto Grossi, Rajeev Raman
Dynamic Compressed Strings with Random Access. 504-515 - Heng Guo, Tyson Williams:
The Complexity of Planar Boolean #CSP with Complex Weights. 516-527 - Tom Gur
Arthur-Merlin Streaming Complexity. 528-539 - Brett Hemenway, Rafail Ostrovsky, Mary Wootters:
Local Correctability of Expander Codes. 540-551 - Martin Hirt, Pavel Raykov:
On the Complexity of Broadcast Setup. 552-563 - Piotr Indyk, Ilya P. Razenshteyn:
On Model-Based RIP-1 Matrices. 564-575 - Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman:
Robust Pseudorandom Generators. 576-588 - Klaus Jansen, Kim-Manuel Klein
A Robust AFPTAS for Online Bin Packing with Polynomial Migration, . 589-600 - Telikepalli Kavitha, Nithin M. Varma
Small Stretch Pairwise Spanners. 601-612 - Eun Jung Kim, Alexander Langer, Christophe Paul
Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions. 613-624 - Vladimir Kolmogorov:
The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization. 625-636 - Christian Konrad, Adi Rosén:
Approximating Semi-matchings in Streaming and in Two-Party Communication. 637-649 - Gregory Kucherov
Full-Fledged Real-Time Indexing for Constant Size Alphabets. 650-660 - Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma:
Arithmetic Circuit Lower Bounds via MaxRank. 661-672 - Michael Lampis:
Model Checking Lower Bounds for Simple Graphs. 673-683 - Massimo Lauria
The Complexity of Proving That a Graph Is Ramsey. 684-695 - Nikos Leonardos:
An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority, . 696-708 - Reut Levi, Dana Ron
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor. 709-720 - Dániel Marx, László A. Végh
Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation. 721-732 - Claire Mathieu, Hang Zhou:
Graph Reconstruction via Distance Oracles. 733-744 - Nicole Megow
Dual Techniques for Scheduling on a Machine with Varying Speed. 745-756 - Gabriel Moruz, Andrei Negoescu:
Improved Space Bounds for Strongly Competitive Randomized Paging Algorithms. 757-768 - Marcin Mucha
No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem. 769-779 - Ryan O'Donnell, Li-Yang Tan:
A Composition Theorem for the Fourier Entropy-Influence Conjecture. 780-791 - Maxim Sviridenko, Justin Ward:
Large Neighborhood Local Search for the Maximum Set Packing Problem. 792-803 - Hannes Uppman
The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom. 804-815 - Yaron Velner:
The Complexity of Infinitely Repeated Alternating Move Games. 816-827 - Oren Weimann
Approximating the Diameter of Planar Graphs in Near Linear Time. 828-839 - Karl Wimmer, Yuichi Yoshida:
Testing Linear-Invariant Function Isomorphism. 840-850
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 2025-01-06 21: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: