default search action
35th STACS 2018: Caen, France
- Rolf Niedermeier, Brigitte Vallée:
35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France. LIPIcs 96, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-062-0 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xvi
- Bruno Salvy
:
Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation. 1:1-1:5 - Meena Mahajan
Lower Bound Techniques for QBF Proof Systems. 2:1-2:8 - Damien Pous:
On the Positive Calculus of Relations with Transitive Closure. 3:1-3:16 - Gerhard J. Woeginger:
The Open Shop Scheduling Problem. 4:1-4:12 - Anna Adamaszek, Antonios Antoniadis, Amit Kumar
Approximating Airports and Railways. 5:1-5:13 - Isolde Adler, Frederik Harwath:
Property Testing for Bounded Degree Databases. 6:1-6:14 - Akanksha Agrawal
Erdös-Pósa Property of Obstructions to Interval Graphs. 7:1-7:15 - Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs:
All Classical Adversary Methods are Equivalent for Total Functions. 8:1-8:14 - Max Bannach, Till Tantau:
Computing Hitting Set Kernels By AC^0-Circuits. 9:1-9:14 - Rémy Belmonte, Michael Lampis, Valia Mitsou:
Parameterized (Approximate) Defective Coloring. 10:1-10:15 - Christoph Berkholz:
The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. 11:1-11:14 - Olaf Beyersdorff
Genuine Lower Bounds for QBF Expansion. 12:1-12:15 - Davide Bilò
Efficient Oracles and Routing Schemes for Replacement Paths. 13:1-13:15 - Davide Bilò
On the Tree Conjecture for the Network Creation Game. 14:1-14:15 - Laurent Bienvenu, Rodney G. Downey:
On Low for Speed Oracles. 15:1-15:13 - Michael Blondin
Large Flocks of Small Birds: on the Minimal Size of Population Protocols. 16:1-16:14 - Benedikt Bollig, Marie Fortin, Paul Gastin:
Communicating Finite-State Machines and Two-Variable Logic. 17:1-17:14 - Marco Bressan
On Approximating the Stationary Distribution of Time-reversible Markov Chains. 18:1-18:14 - Clément Carbonnel
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns. 19:1-19:15 - Bernadette Charron-Bost, Shlomo Moran:
The Firing Squad Problem Revisited. 20:1-20:14 - Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. 21:1-21:15 - Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, Tatiana Starikovskaya:
Upper and Lower Bounds for Dynamic Data Structures on Strings. 22:1-22:14 - Debarati Das, Michal Koucký
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. 23:1-23:14 - Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy:
Solving the Rubik's Cube Optimally is NP-complete. 24:1-24:13 - Gökalp Demirci, Henry Hoffmann, David H. K. Kim:
Approximation Algorithms for Scheduling with Resource and Precedence Constraints. 25:1-25:14 - Pavel Dvorák
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices. 26:1-26:15 - László Egri, Dániel Marx, Pawel Rzazewski
Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization. 27:1-27:15 - Eduard Eiben, Robert Ganian, Sebastian Ordyniak
Small Resolution Proofs for QBF using Dependency Treewidth. 28:1-28:15 - Eduard Eiben, Mithilesh Kumar
Lossy Kernels for Connected Dominating Set on Sparse Graphs. 29:1-29:15 - Lukas Fleischer, Manfred Kufleitner:
The Intersection Problem for Finite Monoids. 30:1-30:14 - Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, Konstantinos Mamouras:
Automata Theory on Sliding Windows. 31:1-31:14 - Moses Ganardi, Daniel König, Markus Lohrey, Georg Zetzsche
Knapsack Problems for Wreath Products. 32:1-32:13 - Robert Ganian, Fabian Klute
On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. 33:1-33:14 - Patrick Gardy, Patricia Bouyer, Nicolas Markey:
Dependences in Strategy Logic. 34:1-34:15 - Serge Gaspers, Shenwei Huang, Daniël Paulusma
Colouring Square-Free Graphs without Long Induced Paths. 35:1-35:15 - Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna:
Optimal Dislocation with Persistent Errors in Subquadratic Time. 36:1-36:13 - George Giakkoupis, Philipp Woelfel:
An Improved Bound for Random Binary Search Trees with Concurrent Insertions. 37:1-37:13 - Garance Gourdel, Tomasz Kociumaka
String Periods in the Order-Preserving Model. 38:1-38:16 - Hiroshi Hirai, Yuni Iwamasa
Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. 39:1-39:14 - John M. Hitchcock
Nonuniform Reductions and NP-Completeness. 40:1-40:13 - Yoichi Iwata, Tomoaki Ogasawara, Naoto Ohsaka
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. 41:1-41:14 - Lars Jaffke
A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. 42:1-42:14 - Sven Jäger
Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling. 43:1-43:14 - Masashi Kiyomi
Space-Efficient Algorithms for Longest Increasing Subsequence. 44:1-44:15 - Chris Köcher
Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid. 45:1-45:14 - Dmitry Kosolobov
Relations Between Greedy and Bit-Optimal LZ77 Encodings. 46:1-46:14 - Denis Kuperberg, Anirban Majumdar
Width of Non-deterministic Automata. 47:1-47:14 - Michael Luttenberger, Raphaela Palenta, Helmut Seidl:
Computing the Longest Common Prefix of a Context-free Language in Polynomial Time. 48:1-48:13 - Benoît Larose, Barnaby Martin
Surjective H-Colouring over Reflexive Digraphs. 49:1-49:14 - Filip Mazowiecki, Cristian Riveros
Pumping Lemmas for Weighted Automata. 50:1-50:14 - André Nies
Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations. 51:1-51:10 - Taku Onodera, Tetsuo Shibuya:
Succinct Oblivious RAM. 52:1-52:16 - Pawel Parys
Recursion Schemes and the WMSO+U Logic. 53:1-53:16 - Aayush Rajasekaran, Jeffrey O. Shallit, Tim Smith
Sums of Palindromes: an Approach via Automata. 54:1-54:12 - Hans Ulrich Simon
On the Containment Problem for Linear Sets. 55:1-55:12 - Marek Szykula
Improving the Upper Bound on the Length of the Shortest Reset Word. 56:1-56:13 - Yasuhiro Takahashi, Seiichiro Tani
Power of Uninitialized Qubits in Shallow Quantum Circuits. 57:1-57:13 - Roei Tell:
Lower Bounds on Black-Box Reductions of Hitting to Density Estimation. 58:1-58:13
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-22 20:20 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: