default search action
42nd STACS 2025: Jena, Germany
- Olaf Beyersdorff
, Michal Pilipczuk
42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025, March 4-7, 2025, Jena, Germany. LIPIcs 327, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2025, ISBN 978-3-95977-365-2 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xxvi
- Albert Atserias:
Proof Complexity and Its Relations to SAT Solving (Invited Talk). 1:1-1:1 - Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver
A Strongly Polynomial Algorithm for Linear Programs with at Most Two Non-Zero Entries per Row or Column (Invited Talk). 2:1-2:1 - Anupam Das:
Algebras for Automata: Reasoning with Regularity (Invited Talk). 3:1-3:1 - Susanna F. de Rezende:
Some Recent Advancements in Monotone Circuit Complexity (Invited Talk). 4:1-4:2 - Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Shaily Verma:
Parameterized Saga of First-Fit and Last-Fit Coloring. 5:1-5:21 - Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, Sebastian Wiederrecht:
Twin-Width One. 6:1-6:19 - Shyan Akmal
Faster Edge Coloring by Partition Sieving. 7:1-7:18 - Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch:
Tropical Proof Systems: Between R(CP) and Resolution. 8:1-8:20 - Sharareh Alipour, Ermiya Farokhnejad, Tobias Mömke:
Improved Approximation Algorithms for (1, 2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model. 9:1-9:17 - Quentin Aristote
Monotone Weak Distributive Laws over the Lifted Powerset Monad in Categories of Algebras. 10:1-10:20 - Srinivasan Arunachalam, Louis Schatzki:
Generalized Inner Product Estimation with Limited Quantum Communication. 11:1-11:17 - Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl
Results on H-Freeness Testing in Graphs of Bounded r-Admissibility. 12:1-12:16 - Samuel Baguley, Yannic Maus, Janosch Ruff, George Skretas:
Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring. 13:1-13:20 - Aritra Banik, Fedor V. Fomin
Multivariate Exploration of Metric Dilation. 14:1-14:17 - Max Bannach, Markus Hecher:
Structure-Guided Automated Reasoning. 15:1-15:18 - Nastaran Behrooznia, Torsten Mütze:
Listing Spanning Trees of Outerplanar Graphs by Pivot-Exchanges. 16:1-16:18 - Matthias Bentert, Fedor V. Fomin
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths. 17:1-17:17 - Marcin Bienkowski, Jaroslaw Byrka, Lukasz Jez:
Online Disjoint Set Covers: Randomization Is Not Necessary. 18:1-18:16 - Benjamin Bordais, Daniel Neider, Rajarshi Roy:
The Complexity of Learning LTL, CTL and ATL Formulas. 19:1-19:20 - Roberto Borelli, Luca Geatti, Marco Montali, Angelo Montanari:
On Cascades of Reset Automata. 20:1-20:22 - Antonin Callard
Computability of Extender Sets in Multidimensional Subshifts. 21:1-21:19 - Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté, Eun Jung Kim, Noleen Köhler:
CMSO-Transducing Tree-Like Graph Decompositions. 22:1-22:18 - Rémy Cerda
How to Play the Accordion: Uniformity and the (Non-)Conservativity of the Linear Approximation of the λ-Calculus. 23:1-23:21 - Keerti Choudhary, Rishabh Dhiman:
A Deterministic Approach to Shortest Path Restoration in Edge Faulty Graphs. 24:1-24:10 - Aleksander Bjørn Grodt Christiansen, Ivor van der Hoog
Local Density and Its Distributed Approximation. 25:1-25:20 - Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin:
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function. 26:1-26:15 - Nathan Claudet, Simon Perdrix:
Local Equivalence of Stabilizer States: A Graphical Characterisation. 27:1-27:18 - Radu Curticapean, Simon Döring, Daniel Neuen, Jiaheng Wang:
Can You Link Up With Treewidth? 28:1-28:24 - Dariusz Dereniowski, Aleksander Lukasiewicz, Przemyslaw Uznanski:
Noisy (Binary) Searching: Simple, Fast and Correct. 29:1-29:18 - Stéphane Devismes, David Ilcinkas, Colette Johnen, Frédéric Mazoit
Being Efficient in Time, Space, and Workload: a Self-Stabilizing Unison and Its Consequences. 30:1-30:18 - Leah Epstein
Efficient Approximation Schemes for Scheduling on a Stochastic Number of Machines. 31:1-31:18 - Nick Fischer, Evangelos Kipouridis
A Faster Algorithm for Constrained Correlation Clustering. 32:1-32:18 - Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney
Metric Dimension and Geodetic Set Parameterized by Vertex Cover. 33:1-33:20 - Pierre Fraigniaud, Minh-Hang Nguyen, Ami Paz:
Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure. 34:1-34:21 - Ameet Gadekar, Tanmay Inamdar:
Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering. 35:1-35:20 - Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity, Saket Saurabh, Roohani Sharma:
MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal. 36:1-36:21 - Jorge Gallego-Hernández, Alessio Mansutti:
On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number. 37:1-37:18 - Arnab Ganguly, Daniel Gibney, Rahul Shah, Sharma V. Thankachan:
Two-Dimensional Longest Common Extension Queries in Compact Space. 38:1-38:17 - Ebrahim Ghorbani, Jonah Leander Hoff, Matthias Mnich:
A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-Like Multigraphs. 39:1-39:19 - Sergey Goncharov
Identity-Preserving Lax Extensions and Where to Find Them. 40:1-40:20 - Jakob Greilhuber
Residue Domination in Bounded-Treewidth Graphs. 41:1-41:20 - Mohit Gurumukhani, Ramamohan Paturi, Michael Saks, Navid Talebanfard:
Local Enumeration: The Not-All-Equal Case. 42:1-42:19 - Sariel Har-Peled, Saladi Rahul:
Approximating Densest Subgraph in Geometric Intersection Graphs. 43:1-43:17 - Tim A. Hartmann, Dániel Marx
Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances. 44:1-44:19 - Deborah Haun, Laura Merker
Forbidden Patterns in Mixed Linear Layouts. 45:1-45:21 - Úrsula Hébert-Johnson, Daniel Lokshtanov:
Sampling Unlabeled Chordal Graphs in Expected Polynomial Time. 46:1-46:20 - Klaus Heeger, Hendrik Molter
Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. 47:1-47:17 - Benjamin Hellouin de Menibus, Pacôme Perrotin:
Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata. 48:1-48:15 - Quentin Hillebrand, Vorapong Suppakitpaisarn, Tetsuo Shibuya:
Cycle Counting Under Local Differential Privacy for Degeneracy-Bounded Graphs. 49:1-49:22 - Martin Hoefer, Conrad Schecker
Designing Exploration Contracts. 50:1-50:19 - Felix Hommelsheim, Zhenwei Liu, Nicole Megow, Guochuan Zhang:
Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures. 51:1-51:21 - Séhane Bel Houari-Durand, Eduard Eiben, Magnus Wahlström:
Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion. 52:1-52:17 - Pavel Hrubes, Pushkar S. Joglekar:
On Read-k Projections of the Determinant. 53:1-53:7 - Stacey Jeffery, Galina Pass:
Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer. 54:1-54:16 - Jean Christoph Jung, Jedrzej Kolodziejski:
Modal Separation of Fixpoint Formulae. 55:1-55:20 - Julia Katheder, Michael Kaufmann, Sergey Pupyrev, Torsten Ueckerdt:
Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs. 56:1-56:18 - Matthias Kaul, Kelin Luo, Matthias Mnich, Heiko Röglin:
Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously. 57:1-57:18 - Piotr Kawalek, Armin Weiß:
Violating Constant Degree Hypothesis Requires Breaking Symmetry. 58:1-58:21 - Yasushi Kawase, Tomohiro Nakayoshi:
Online Matching with Delays and Size-Based Costs. 59:1-59:18 - Amirhossein Kazeminia, Andrei A. Bulatov:
Modular Counting CSP: Reductions and Algorithms. 60:1-60:18 - Stefan Kiefer, Andrew Ryzhikov:
Efficiently Computing the Minimum Rank of a Matrix in a Monoid of Zero-One Matrices. 61:1-61:22 - Tomohiro Koana, Magnus Wahlström:
Faster Algorithms on Linear Delta-Matroids. 62:1-62:19 - Petr Kolman:
Approximation of Spanning Tree Congestion Using Hereditary Bisection. 63:1-63:6 - Manuel Lafond, Alitzel López Sánchez, Weidong Luo:
Cluster Editing on Cographs and Related Classes. 64:1-64:21 - Yuwei Liu, Yijia Chen, Shuangle Li, Bingkai Lin, Xin Zheng:
On Average Baby PIH and Its Applications. 65:1-65:19 - Bruno Loff, Alexey Milovanov:
The Hardness of Decision Tree Complexity. 66:1-66:13 - Aliaume Lopez:
Commutative ℕ-Rational Series of Polynomial Growth. 67:1-67:16 - Lê Thành Dung Nguyên, Gabriele Vanoni:
Slightly Non-Linear Higher-Order Tree Transducers. 68:1-68:20 - Damian Niwinski, Pawel Parys, Michal Skrzypczak:
A Dichotomy Theorem for Ordinal Ranks in MSO. 69:1-69:18 - Boaz Patt-Shamir, Adi Rosén, Seeun William Umboh
Colorful Vertex Recoloring of Bipartite Graphs. 70:1-70:19 - Patrick Schnider, Linus Stalder, Simon Weber
Unfairly Splitting Separable Necklaces. 71:1-71:19 - Kazumasa Shinagawa, Koji Nuida:
Card-Based Protocols Imply PSM Protocols. 72:1-72:18 - Anastasiia Tkachenko, Haitao Wang:
Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position. 73:1-73:20 - Noam Touitou
Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay. 74:1-74:21 - Oleg Verbitsky, Maksim Zhukovskii:
Canonical Labeling of Sparse Random Graphs. 75:1-75:20 - Haitao Wang, Yiming Zhao:
Dynamic Unit-Disk Range Reporting. 76:1-76:19
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-11-14 22:25 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: