default search action
30th STACS 2013: Kiel, Germany
- Natacha Portier, Thomas Wilke:
30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany. LIPIcs 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2013, ISBN 978-3-939897-50-7
Papers
- Natacha Portier, Thomas Wilke:
Frontmatter, Table of Contents, Preface, Workshop Organization. - Kousha Etessami:
The complexity of analyzing infinite-state Markov chains, Markov decision processes, and stochastic games (Invited talk). 1-2 - Nicolas Bousquet
, Aurélie Lagoutte, Stéphan Thomassé:
Graph coloring, communication complexity and the stubborn problem (Invited talk). 3-4 - Kurt Mehlhorn:
Physarum Computations (Invited talk). 5-6 - Dániel Marx:
Algorithmic Graph Structure Theory (Tutorial). 7-7 - Fedor V. Fomin
Searching for better fill-in. 8-19 - Andreas Björklund, Petteri Kaski, Lukasz Kowalik
Probably Optimal Graph Motifs. 20-31 - Fedor V. Fomin
Tight bounds for Parameterized Complexity of Cluster Editing. 32-43 - Albert Atserias, Sergi Oliva:
Bounded-width QBF is PSPACE-complete. 44-54 - Daniël Paulusma
Model Counting for CNF Formulas of Bounded Modular Treewidth. 55-66 - Serge Gaspers, Sebastian Ordyniak
Backdoors to q-Horn. 67-79 - Stefan Kratsch:
On Polynomial Kernels for Sparse Integer Linear Programs. 80-91 - Fedor V. Fomin
Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. 92-103 - Martijn Baartse, Klaus Meer:
The PCP theorem for NP over the reals. 104-115 - Adam Case, Jack H. Lutz:
Mutual Dimension. 116-126 - Yoichi Iwata, Yuichi Yoshida:
Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra. 127-138 - Konstantin Makarychev:
Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs. 139-147 - Xi Chen, Martin E. Dyer
The complexity of approximating conservative counting CSPs. 148-159 - Yuval Ishai, Eyal Kushilevitz, Omer Strulovich:
Lossy Chains and Fractional Secret Sharing. 160-171 - Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz
Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. 172-184 - Malte Darnstädt, Hans Ulrich Simon
Unlabeled Data Does Provably Help. 185-196 - Michal Pilipczuk
Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings. 197-208 - Marek Cygan
On Pairwise Spanners. 209-220 - Jisu Jeong, O-joung Kwon
Excluded vertex-minors for graphs of linear rank-width at most k. 221-232 - Artur Jez
Recompression: a simple and powerful technique for word equations. 233-244 - Tomasz Kociumaka
Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries. 245-256 - Pawel Gawrychowski, Florin Manea, Robert Mercas, Dirk Nowotka
Finding Pseudo-repetitions. 257-268 - Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, Andrew Winslow:
Algorithms for Designing Pop-Up Cards. 269-280 - Luis Barba, Matias Korman, Stefan Langerman
Space-Time Trade-offs for Stack-Based Algorithms. 281-292 - Danny Z. Chen, Haitao Wang:
L_1 Shortest Path Queries among Polygonal Obstacles in the Plane. 293-304 - Manfred Kufleitner
Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable. 305-316 - Wieslaw Szwast, Lidia Tendera
FO^2 with one transitive relation is decidable. 317-328 - Luc Dartois
Two-variable first order logic with modular predicates over words. 329-340 - Magnus Wahlström
Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem. 341-352 - Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen:
Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs. 353-364 - Florent Capelli
The arithmetic complexity of tensor contractions. 365-376 - Edith Hemaspaandra, Lane A. Hemaspaandra
Search versus Decision for Election Manipulation Problems. 377-388 - Leah Epstein
Improved Bounds for Online Preemptive Matching. 389-399 - Markus Jalsenius, Benny Porat, Benjamin Sach
Parameterized Matching in the Streaming Model. 400-411 - Meghana Nasre
Popular Matchings: Structure and Cheating Strategies. 412-423 - Hartmut Klauck
Fooling One-Sided Quantum Protocols. 424-433 - Loïck Magnin, Jérémie Roland
Explicit relation between all lower bound techniques for quantum query complexity. 434-445 - Andris Ambainis, Arturs Backurs, Juris Smotrovs
Optimal quantum query bounds for almost all Boolean functions. 446-453 - Nathanaël François, Frédéric Magniez:
Streaming Complexity of Checking Priority Queues. 454-465 - Konstantin Kutzkov:
Deterministic algorithms for skewed matrix products. 466-477 - Tengyu Ma, Bo Tang, Yajun Wang:
The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems. 478-489 - Emmanuel Jeandel, Pascal Vanier
Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type. 490-501 - Ines Klimann:
The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable. 502-513 - Amir M. Ben-Amram:
Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract). 514-525 - Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks:
On the practically interesting instances of MAXCUT. 526-537 - György Dósa, Jirí Sgall
First Fit bin packing: A tight analysis. 538-549 - Amin Karbasi, Morteza Zadimoghaddam:
Constrained Binary Identification Problem. 550-561 - Mikolaj Bojanczyk, Tomasz Idziaszek, Michal Skrzypczak:
Regular languages of thin trees. 562-573 - Thomas Colcombet, Laure Daviaud
Approximate comparison of distance automata. 574-585 - Martin Huschenbett:
The Rank of Tree-Automatic Linear Orderings. 586-597 - Julien Clément
A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms. 598-609 - Mark Braverman, Gal Oshri:
Search using queries on indistinguishable items. 610-621 - Balagopal Komarath, Jayalal Sarma:
Pebbling, Entropy and Branching Program Size Lower Bounds. 622-633 - Thomas Watson:
Advice Lower Bounds for the Dense Model Theorem. 634-645 - Natacha Portier, Thomas Wilke:
Author Index. 646-647
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-11-16 00:13 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: