Accepted papers

STACS 2018 Accepted Papers

Dmitry Kosolobov. Relations Between Greedy and Bit-Optimal LZ77 Encodings
Chris Köcher. Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid
Marek Szykuła. Improving the upper bound on the length of the shortest reset words
Michael Luttenberger, Raphaela Palenta and Helmut Seidl. Computing the longest common prefix of a context-free language in polynomial time
Taku Onodera and Tetsuo Shibuya. Succinct Oblivious RAM
Lukas Fleischer and Manfred Kufleitner. The Intersection Problem for Finite Monoids
Clément Carbonnel, David A. Cohen, Martin C. Cooper and Stanislav Živný. On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
Paweł Parys. Recursion Schemes and the WMSO+U Logic
Andre Nies and Frank Stephan. Closure of resource-bounded randomness notions under polynomial time permutations
Aayush Rajasekaran, Tim Smith and Jeffrey Shallit. Sums of Palindromes: an Approach via Automata
Laurent Bienvenu and Rod Downey. On low for speed oracles
Filip Mazowiecki and Cristian Riveros. Pumping lemmas for weighted automata
Rémy Belmonte, Michael Lampis and Valia Mitsou. Parameterized (Approximate) Defective Coloring
Roei Tell. Lower Bounds on Black-Box Reductions of Hitting to Density Estimation
Erik D. Demaine, Sarah Eisenstat and Mikhail Rudoy. Solving the Rubik's Cube Optimally is NP-complete
Yasuhiro Takahashi and Seiichiro Tani. Power of Uninitialized Qubits in Shallow Quantum Circuits
Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar and Pavel Veselý. Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Davide Bilò, Keerti Choudhary, Luciano Gualà, Stefano Leucci, Merav Parter and Guido Proietti. Efficient Oracles and Routing Schemes for Replacement Paths
Andris Ambainis, Mārtiņš Kokainis, Krišjānis Prūsis and Jevgēnijs Vihrovs. All Classical Adversary Methods are Equivalent for Total Functions
Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer and Jun Tarui. Space-Efficient Algorithms for Longest Increasing Subsequence
Raphael Clifford, Allan Grønlund, Kasper Green Larsen and Tatiana Starikovskaya. Upper and lower bounds for dynamic data structures on strings
Sven Jäger and Martin Skutella. Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling
Max Bannach and Till Tantau. Computing Hitting Set Kernels By AC$^0$-Circuits
Eduard Eiben, Robert Ganian and Sebastian Ordyniak. Small Resolution Proofs for QBF using Dependency Treewidth
Bernadette Charron-Bost and Shlomo Moran. The Firing Squad Problem Revisited
Moses Ganardi, Daniel König, Markus Lohrey and Georg Zetzsche. Knapsack problems for wreath products
Barnaby Martin, Daniel Paulusma and Benoit Larose. Surjective H-Colouring over Reflexive Digraphs
Lars Jaffke, O-Joung Kwon and Jan Arne Telle. A unified polynomial-time algorithm for Feedback Vertex Set on graphs of bounded mim-width
Robert Ganian, Fabian Klute and Sebastian Ordyniak. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey and Konstantinos Mamouras. Automata theory on sliding windows
Laszlo Egri, Dániel Marx and Paweł Rzążewski. Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization
Suryajith Chillara, Nutan Limaye and Srikanth Srinivasan. Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
Marco Bressan, Enoch Peserico and Luca Pretto. On approximating the stationary distribution of time-reversible Markov chains
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur and Tomasz Walen. String Periods in the Order-Preserving Model
Denis Kuperberg and Anirban Majumdar. Width of Non-deterministic Automata
Anna Adamaszek, Antonios Antoniadis, Amit Kumar and Tobias Mömke. Approximating Airports and Railways
Olaf Beyersdorff and Joshua Blinkhorn. Genuine Lower Bounds for QBF Expansion
Hans Simon. On the Containment Problem for Linear Sets
Michael Blondin, Javier Esparza and Stefan Jaax. Large Flocks of Small Birds: On the Minimal Size of Population Protocols
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu and Paolo Penna. Optimal dislocation with persistent errors in subquadratic time
Benedikt Bollig, Marie Fortin and Paul Gastin. Communicating Finite-State Machines and Two-Variable Logic
Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota and Stanislav Zivny. Beyond JWP: A tractable class of binary VCSPs via M-convex intersection
John M. Hitchcock and Hadi Shafei. Nonuniform Reductions and NP-Completeness
Yoichi Iwata, Tomoaki Ogasawara and Naoto Ohsaka. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
Eduard Eiben, Mithilesh Kumar, Amer Mouawad, Fahad Panolan and Sebastian Siebertz. Lossy Kernels for Connected Dominating Set
Gokalp Demirci, Henry Hoffmann and David Kim. Approximation Algorithms for Scheduling with Resource and Precedence Constraints
Serge Gaspers, Shenwei Huang and Daniel Paulusma. Colouring Square-Free Graphs without Long Induced Paths
George Giakkoupis and Philipp Woelfel. An Improved Bound for Random Binary Search Trees with Concurrent Insertions
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Erdős–Pósa Property of Obstructions to Interval Graphs
Isolde Adler and Frederik Harwath. Property Testing for Bounded Degree Databases
Davide Bilò and Pascal Lenzner. On the Tree Conjecture for the Network Creation Game
Patrick Gardy, Patricia Bouyer and Nicolas Markey. Dependences in Strategy Logic
Debarati Das, Michal Koucky and Mike Saks. Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
Christoph Berkholz. The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs
Online user: 1 RSS Feed