Planning

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)