You can download the programme of the conference in PDF format: STACS program.

Wednesday, February 28

  • 14:00-15:00 Registration (S3-037)
  • 15:00-18:00 Tutorial Bruno Salvy (S3-044). Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation
  • 19:00-22:00 Welcome reception (Dôme, town center)

Thursday, March 1

  • 8:30-9:00 Registration
  • 9:00-9:15 Welcome
  • 9:15-10:15 Plenary talk (I) Meena Mahajan (S3-049). Lower bound techniques for QBF proof systems
  • 10:15-10:30 Coffee break
  • 10:30-11:45 Parallel sessions (1A and 1B)
    Session 1A (S3-044)
    • Clément Carbonnel, David A. Cohen, Martin C. Cooper and Stanislav Zivny. On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
    • Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota and Stanislav Zivny. Beyond JWP: A tractable class of binary VCSPs via M-convex intersection
    • Isolde Adler and Frederik Harwath. Property Testing for Bounded Degree Databases
    Session 1B (S3-045)
    • Yoichi Iwata, Tomoaki Ogasawara and Naoto Ohsaka. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
    • Barbara Geissmann, Stefano Leucci, Chih-Hung Liu and Paolo Penna. Optimal dislocation with persistent errors in subquadratic time
    • Davide Bilò, Keerti Choudhary, Luciano Gualà, Stefano Leucci, Merav Parter and Guido Proietti. Efficient Oracles and Routing Schemes for Replacement Paths
  • 11:45-12:00 Coffee break (S3-037)
  • 12:00-13:15 Parallel sessions (2A and 2B)
    Session 2A (S3-044)
    • André Nies and Frank Stephan. Closure of resource-bounded randomness notions under polynomial time permutations
    • Laurent Bienvenu and Rod Downey. On low for speed oracles
    • John M. Hitchcock and Hadi Shafei. Nonuniform Reductions and NP-Completeness
    Session 2B (S3-045)
    • Robert Ganian, Fabian Klute and Sebastian Ordyniak. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
    • Hans Simon. On the Containment Problem for Linear Sets
    • Debarati Das, Michal Koucky and Mike Saks. Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication
  • 13:15-14:45 Lunch S3-037 (Campus 2)
  • 14:45-16:00 Parallel sessions (3A and 3B)
    Session 3A (S3-044)
    • 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
    • Max Bannach and Till Tantau. Computing Hitting Set Kernels By AC$^0$-Circuits
    • Eduard Eiben, Mithilesh Kumar, Amer Mouawad, Fahad Panolan and Sebastian Siebertz. Lossy Kernels for Connected Dominating Set
    Session 3B (S3-045)
    • Bernadette Charron-Bost and Shlomo Moran. The Firing Squad Problem Revisited
    • Marek Szykula. Improving the upper bound on the length of the shortest reset words
    • Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey and Konstantinos Mamouras. Automata theory on sliding windows
  • 16:00-16:15 Coffee break (S3-037)
  • 16:15-17:30 Parallel sessions (4A and 4B)
    Session 4A (S3-044)
    • Sven Jäger and Martin Skutella. Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling
    • Anna Adamaszek, Antonios Antoniadis, Amit Kumar and Tobias Mömke. Approximating Airports and Railways
    • Gokalp Demirci, Henry Hoffmann and David Kim. Approximation Algorithms for Scheduling with Resource and Precedence Constraints
    Session 4B (S3-045)
    • Aayush Rajasekaran, Tim Smith and Jeffrey Shallit. Sums of Palindromes: an Approach via Automata
    • Filip Mazowiecki and Cristian Riveros. Pumping lemmas for weighted automata
    • Denis Kuperberg and Anirban Majumdar. Width of Non-deterministic Automata
  • 18:30-20:00 Walking city tour of Caen with a guide
  • Free evening

Friday, March 2

  • 9:00-10:00 Plenary talk (II) Damien Pous (S3-049). On the positive calculus of relations with transitive closure
  • 10:00-10:15 Coffee break
  • 10:15-11:30 Parallel sessions (5A and 5B)
    Session 5A (S3-044)
    • Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer and Jun Tarui. Space-Efficient Algorithms for Longest Increasing Subsequence
    • Dmitry Kosolobov. Relations Between Greedy and Bit-Optimal LZ77 Encodings
    • Michael Luttenberger, Raphaela Palenta and Helmut Seidl. Computing the longest common prefix of a context-free language in polynomial time
    Session 5B (S3-045)
    • Roei Tell. Lower Bounds on Black-Box Reductions of Hitting to Density Estimation
    • Andris Ambainis, Mārtiņš Kokainis, Krišjānis Prūsis and Jevgēnijs Vihrovs. All Classical Adversary Methods are Equivalent for Total Functions
    • Yasuhiro Takahashi and Seiichiro Tani. Power of Uninitialized Qubits in Shallow Quantum Circuits
  • 11:30-11:45 Coffee break (S3-037)
  • 11:45-13:00 Parallel sessions (6A and 6B)
    Session 6A (S3-044)
    • Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur and Tomasz Walen. String Periods in the Order-Preserving Model
    • Raphael Clifford, Allan Grønlund, Kasper Green Larsen and Tatiana Starikovskaya. Upper and lower bounds for dynamic data structures on strings
    • Taku Onodera and Tetsuo Shibuya. Succinct Oblivious RAM
    Session 6B (S3-045)
    • Michael Blondin, Javier Esparza and Stefan Jaax. Large Flocks of Small Birds: On the Minimal Size of Population Protocols
    • Christoph Berkholz. The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs
    • Lukas Fleischer and Manfred Kufleitner. The Intersection Problem for Finite Monoids
  • 13:00-14:15 Lunch S3-037 (Campus 2 )
  • 14:15-15:30 Parallel sessions (7A and 7B)
    Session 7A (S3-044)
    • Olaf Beyersdorff and Joshua Blinkhorn. Genuine Lower Bounds for QBF Expansion
    • Eduard Eiben, Robert Ganian and Sebastian Ordyniak. Small Resolution Proofs for QBF using Dependency Treewidth
    • Chris Köcher. Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid
    Session 7B (S3-045)
    • Rémy Belmonte, Michael Lampis and Valia Mitsou. Parameterized (Approximate) Defective Coloring
    • Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Erdös-Polya Property of Obstructions to Interval Graphs
    • Laszlo Egri, Dániel Marx and Paweł Rzążewski. Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization
  • 15:30 Departure (by bus) for Bayeux tapestry excursion
  • 16:30-18:30 Bayeux tapestry visit
  • 19:30 Conference dinner (at Château de Creully)

Saturday, March 3

  • 9:00-10:00 Plenary talk (III) Gerhard Woeginger (S3-049). The open shop scheduling problem
  • 10:00-10:15 Coffee break
  • 10:15-11:30 Parallel sessions (8A and 8B)
    Session 8A (S3-044)
    • Benedikt Bollig, Marie Fortin and Paul Gastin. Communicating Finite-State Machines and Two-Variable Logic
    • Pawel Parys. Recursion Schemes and the WMSO+U Logic
    • Patrick Gardy, Patricia Bouyer and Nicolas Markey. Dependences in Strategy Logic
    Session 8B (S3-045)
    • Suryajith Chillara, Nutan Limaye and Srikanth Srinivasan. Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
    • Erik D. Demaine, Sarah Eisenstat and Mikhail Rudoy. Solving the Rubik's Cube Optimally is NP-complete
    • Moses Ganardi, Daniel König, Markus Lohrey and Georg Zetzsche. Knapsack problems for wreath products
  • 11:30-11:45 Coffee break (S3-037)
  • 11:45-13:00 Parallel sessions (9A and 9B)
    Session 9A (S3-044)
    • Marco Bressan, Enoch Peserico and Luca Pretto. On approximating the stationary distribution of time-reversible Markov chains
    • George Giakkoupis and Philipp Woelfel. An Improved Bound for Random Binary Search Trees with Concurrent Insertions
    • Davide Bilò and Pascal Lenzner. On the Tree Conjecture for the Network Creation Game
    Session 9B (S3-045)
    • 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
    • Serge Gaspers, Shenwei Huang and Daniel Paulusma. Colouring Square-Free Graphs without Long Induced Paths
  • 13:00-14:15 Light meal (Campus 2)
Online user: 1 RSS Feed