STACS

42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Jena, March 04-07, 2025

Schedule

Jump to: [Tuesday] [Wednesday] [Thursday] [Friday]

Click to expand pre-conference workshop
Monday, March 03 (pre-conference workshop)
13.30 - 14.30
Heribert Vollmer. The Complexity of Enumerating Satisfying Assignments (invited talk) [slides]
14.30 - 15.00
Coffee break
15.00 - 16.20
Contributed talks 1
15.00
Manuel Bodirsky. Reducing Stochastic Games to Semidefinite Programming [slides]
15.20
Laura Strieker. Graph Neural Networks and Arithmetic Circuits [slides]
15.40
Andrew Ryzhikov. The complexity of computing the period and the exponent of a digraph [slides]
16.00
Fabian Egidy. Optimal Proof Systems for Complex Sets are Hard to Find [slides]
16.20 - 16.50
Coffee break
16.50 - 17.50
Contributed talks 2
16.50
Pascal Lenzner. Dynamics of Schelling Games [slides]
17.10
Santiago Guzmán Pro. Hereditary First-Order Logic and Extensional ESO [slides]
17.30
Arne Meier. Rejection in Abstract Argumentation: Harder Than Acceptance? [slides]
18.00 - 18.30
Business Meeting of the GI groups
Tuesday, March 04 (pre-conference workshop)
09.15 - 10.15
Sebastian Wild. Quicksort, Timsort, Powersort - Algorithmic ideas, engineering tricks, and trivia behind CPython’s new sorting algorithm (invited talk) [slides]
10.15 - 10.45
Coffee break
10.45 - 12.05
Contributed talks 3
10.45
Marlene Gründel. On the Parameterized Complexity of Graph Modification to First-Order Logic Properties [slides]
11.05
André Nichterlein. Parameterized Complexity of Segment Routing [slides]
11.25
Ilya Chernykh. On the Tightness of the Standard Lower Bound in the Two-Machine Routing Open Shop [slides]
11.45
Florian Bruse. Categorizing Ensembles of Real-Valued Functions [slides]
12.05 - 13.30
Lunch break
Tuesday, March 04
13.30 - 13.40
Opening [slides]
13.40 - 14.30
Albert Atserias. Proof complexity and its relations to SAT solving (tutorial, part 1) [slides] Chair: Olaf Beyersdorff
14.30 - 15.00
Coffee break
15.00 - 15.10
Address of the president of Friedrich Schiller University Jena
15.10 - 16.00
Albert Atserias. Proof complexity and its relations to SAT solving (tutorial, part 2) [slides] Chair: Olaf Beyersdorff
16.00 - 16.30
Coffee break
16.30 - 17.50
Distributed algorithms and communication Chair: Sebastian Wild
Logic and complexity Chair: Manuel Bodirsky
16.30
Stéphane Devismes, David Ilcinkas, Colette Johnen and Fréderic Mazoit. Being Efficient in Time, Space, and Workload: a Self-stabilizing Unison and its Consequences [slides]
Yaroslav Alekseev, Dima Grigoriev and Edward A. Hirsch. Tropical Proof Systems: Between R(CP) and Resolution [slides]
16.50
Aleksander Bjoern Grodt Christiansen, Ivor van der Hoog and Eva Rotenberg. Local Density and its Distributed Approximation [slides]
Jorge Gallego and Alessio Mansutti. On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number [slides]
17.10
Pierre Fraigniaud, Minh Hang Nguyen and Ami Paz. Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure [slides]
Benjamin Bordais, Daniel Neider and Rajarshi Roy. The Complexity of Learning LTL, CTL and ATL formulas [slides]
17.30
Kazumasa Shinagawa and Koji Nuida. Card-Based Protocols Imply PSM Protocols [slides]
Ebrahim Ghorbani, Jonah Leander Hoff and Matthias Mnich. Generalized Arrival on Tree-Like Multigraphs [slides]
18.30 - 23.00
Reception (Volkshaus)
Wednesday, March 05
09.15 - 10.15
Daniel Dadush. A Strongly Polynomial Algorithm for Linear Programs with at most Two Non-zero Entries per Row or Column (invited talk) [slides] Chair: Nguyen Kim Thang
10.15 - 10.45
Coffee break
10.45 - 12.05
Resilience and robustness Chair: Magnus Wahlström
Algebra, logic and computability Chair: Andrei Bulatov
10.45
Felix Hommelsheim, Zhenwei Liu, Nicole Megow and Guochuan Zhang. Protecting the Connectivity of a Graph under Non-uniform Edge Failures [slides]
Quentin Aristote. Monotone weak distributive laws over the lifted powerset monad in categories of algebras [slides]
11.05
Keerti Choudhary and Rishabh Dhimann. A Deterministic Approach to Shortest Path Restoration in Edge Faulty Graphs [slides]
Sergey Goncharov, Dirk Hofmann, Pedro Nora, Lutz Schröder and Paul Wild. Identity-Preserving Lax Extensions and Where to Find Them [slides]
11.25
Petr Kolman. Approximation of Spanning Tree Congestion Using Hereditary Bisection [slides]
Rémy Cerda and Lionel Vaux Auclair. How to play the Accordion: Uniformity and the (non-)conservativity of the linear approximation of the λ-calculus [slides]
11.45
Quentin Hillebrand, Vorapong Suppakitpaisarn and Tetsuo Shibuya. Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs [slides]
Antonin Callard, Léo Paviet Salomon and Pascal Vanier. Computability of extender sets in multidimensional subshifts [slides]
12.05 - 13.30
Lunch break
13.30 - 15.10
Parameterized algorithms I Chair: Arne Meier
Automata Chair: Sylvain Schmitz
13.30
Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Shaily Verma. Parameterized Saga of First-Fit and Last-Fit Coloring [slides]
Benjamin Hellouin de Menibus and Pacôme Perrotin. Alternating hierarchy of subshifts defined by nondeterministic plane-walking automata [slides]
13.50
Tomohiro Koana and Magnus Wahlström. Faster algorithms on linear delta-matroids [slides]
Roberto Borelli, Luca Geatti, Marco Montali and Angelo Montanari. On Cascades of Reset Automata [slides]
14.10
Matthias Bentert, Fedor Fomin and Petr Golovach. Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths [slides]
Aliaume Lopez. Commutative N-rational series of polynomial growth [slides]
14.30
Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity, Saket Saurabh and Roohani Sharma. MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal [slides]
Stefan Kiefer and Andrew Ryzhikov. Efficiently computing the minimum rank of a matrix in a monoid of zero-one matrices [slides]
14.50
Eduard Eiben, Séhane Bel Houari-Durand and Magnus Wahlström. Polynomial kernel and incompressibility for Prison-Free Edge Deletion and Completion [slides]
Lê Thành Dũng Nguyễn and Gabriele Vanoni. Slightly non-linear higher-order tree transducers (online) [slides]
15.10 - 15.40
Coffee break
15.40 - 17.20
Parameterized algorithms II Chair: Nils Morawietz
Computational geometry and scheduling Chair: Christian Komusiewicz
15.40
Jakob Greilhuber, Philipp Schepper and Philip Wellnitz. Residue Domination in Bounded-Treewidth Graphs
Haitao Wang and Yiming Zhao. Dynamic Unit-Disk Range Reporting (online) [slides]
16.00
Tim A. Hartmann and Dániel Marx. Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances [slides]
Anastasiia Tkachenko and Haitao Wang. Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position (online) [slides]
16.20
Radu Curticapean, Simon Döring, Daniel Neuen and Jiaheng Wang. Can You Link Up With Treewidth? [slides]
Sariel Har-Peled and Saladi Rahul. Approximating Densest Subgraph in Geometric Intersection Graphs [slides]
16.40
Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma and Prafullkumar Tale. Metric Dimension and Geodetic Set Parameterized by Vertex Cover [slides]
Leah Epstein and Asaf Levin. Efficient approximation schemes for scheduling on a stochastic number of machines [slides]
17.00
Aritra Banik, Fedor Fomin, Petr Golovach, Tanmay Inamdar, Satyabrata Jana and Saket Saurabh. Multivariate Exploration of Metric Dilation [slides]
Klaus Heeger and Hendrik Molter. Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines [slides]
17.30 - 18.30
Business Meeting [slides 1] [slides 2]
Thursday, March 06
09.15 - 10.15
Anupam Das. Algebras for automata: reasoning with regularity (invited talk) [slides] Chair: Dietrich Kuske
10.15 - 10.45
Coffee break
10.45 - 12.05
Miscellaneous graph algorithms Chair: Edward Hirsch
Logic Chair: Navid Talebanfard
10.45
Shyan Akmal and Tomohiro Koana. Faster Edge Coloring by Partition Sieving [slides]
Jean Christoph Jung and Jędrzej Kołodziejski. Modal Separation of Fixpoint Formulae [slides]
11.05
Nastaran Behrooznia and Torsten Mütze. Listing spanning trees of outerplanar graphs by pivot exchanges [slides]
Damian Niwiński, Paweł Parys and Michał Skrzypczak. A Dichotomy Theorem for Ordinal Ranks in MSO [slides]
11.25
Ursula Hebert-Johnson and Daniel Lokshtanov. Sampling Unlabeled Chordal Graphs in Expected Polynomial Time [slides]
Max Bannach and Markus Hecher. Structure-Guided Automated Reasoning [slides]
11.45
Boaz Patt-Shamir, Adi Rosén and Seeun William Umboh. Colorful Vertex Recoloring of Bipartite Graphs [slides]
Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté, Eun Jung Kim and Noleen Köhler. CMSO-transducing tree-like graph decompositions [slides]
12.05 - 13.30
Lunch break
13.30 - 15.10
Complexity I Chair: Heribert Vollmer
Online, streaming, and low-space algorithms Chair: Thomas Schwentick
13.30
Alexey Milovanov and Bruno Loff. The hardness of decision tree complexity (online) [slides]
Yasushi Kawase and Tomohiro Nakayoshi. Online Matching with Delays and Size-based Costs [slides]
13.50
Mohit Jayanti Gurumukhani, Ramamohan Paturi, Michael Saks and Navid Talebanfard. Local Enumeration: The Not-All-Equal Case [slides]
Noam Touitou. Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay [slides]
14.10
Andrei Bulatov and Amirhossein Kazeminia. Modular Counting CSP: Reductions and Algorithms
Marcin Bienkowski, Jaroslaw Byrka and Łukasz Jeż. Online Disjoint Set Covers: Randomization is not Necessary [slides]
14.30
Yuwei Liu, Yijia Chen, Shuangle Li, Bingkai Lin and Xin Zheng. On Average Baby PIH and Its Applications [slides]
Sharareh Alipour, Ermiya Farokhnejad and Tobias Momke. Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model [slides]
14.50
Pavel Hrubes and Pushkar Joglekar. On read-k projections of the determinant [slides]
Daniel Gibney, Sharma V. Thankachan, Arnab Ganguly and Rahul Shah. Two-Dimensional Longest Common Extension Queries in Compact Space [slides]
15.10 - 15.40
Coffee break
15.40 - 17.20
Complexity II Chair: Till Tantau
Exploration and random graphs Chair: Jacobo Toran
15.40
Nathan Claudet and Simon Perdrix. Local equivalence of stabilizer states: a graphical characterisation [slides]
Patrick Schnider, Linus Stalder and Simon Weber. Unfairly Splitting Separable Necklaces [slides]
16.00
Stacey Jeffery and Galina Pass. Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer [slides]
Dariusz Dereniowski, Aleksander Łukasiewicz and Przemysław Uznański. Noisy (binary) searching: simple, fast and correct [slides]
16.20
Srinivasan Arunachalam and Louis Schatzki. Generalized Inner Product Estimation with Limited Quantum Communication [slides]
Martin Hoefer, Conrad Schecker and Kevin Schewior. Designing Exploration Contracts [slides]
16.40
Piotr Kawałek and Armin Weiß. Violating Constant Degree Hypothesis Requires Breaking Symmetry [slides]
Oleg Verbitsky and Maksim Zhukovskii. Canonical labeling of sparse random graphs [slides]
17.00
Nikolai Chukhin, Alexander Kulikov and Ivan Mihajlin. Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function [slides]
Samuel Baguley, Yannic Maus, Janosch Ruff and George Skretas. Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring [slides]
18.30 - 23.00
Conference Dinner (Volksbad)
Friday, March 07
09.15 - 10.15
Susanna F. de Rezende. Some Recent Advancements in Monotone Circuit Complexity (invited talk) [slides] Chair: Olaf Beyersdorff
10.15 - 10.45
Coffee break
10.45 - 12.15
Graphs with structure Chair: Dominik Scheder
Clustering Chair: Rüdiger Reischuk
10.45
Julia Katheder, Michael Kaufmann, Sergey Pupyrev and Torsten Ueckerdt. Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs (online)
Nick Fischer, Evangelos Kipouridis, Jonas Klausen and Mikkel Thorup. A Faster Algorithm for Constrained Correlation Clustering [slides]
11.05
Deborah Haun, Laura Merker and Sergey Pupyrev. Forbidden Patterns in Mixed Linear Layouts [slides]
Ameet Gadekar and Tanmay Inamdar. Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering [slides]
11.25
Christine Awofeso, Patrick Greaves, Oded Lachish and Felix Reidl. Results on H-freeness testing in graphs of bounded r-admissibility [slides]
Matthias Kaul, Kelin Luo, Matthias Mnich and Heiko Röglin. Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously [slides]
11.45
Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald and Sebastian Wiederrecht. Twin-width one [slides]
Manuel Lafond, Alitzel López Sánchez and Weidong Luo. Cluster Editing on Cographs and Related Classes [slides]