default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID50th MFCS 2025: Warsaw, Poland
- Pawel Gawrychowski
, Filip Mazowiecki, Michal Skrzypczak:
50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, Warsaw, Poland, August 25-29, 2025. LIPIcs 345, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2025, ISBN 978-3-95977-388-1 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xviii
- Thomas Colcombet:
Lambdas, Transducers and MSO (Invited Talk). 1:1-1:1 - Giuseppe F. Italiano:
Higher Connectivity in Directed Graphs (Invited Talk). 2:1-2:4 - Rasmus Kyng:
Almost-Linear Time Algorithms for Partially Dynamic Graphs (Invited Talk). 3:1-3:1 - Filip Murlak:
On Graph Queries and Modal Constraints (Invited Talk). 4:1-4:1 - Anca Muscholl:
On Synthesis of Distributed Monitors (Invited Talk). 5:1-5:3 - Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, Antoine Vinciguerra:
Catalytic Computing and Register Programs Beyond Log-Depth. 6:1-6:18 - Morteza Alimi, Tobias Mömke, Michael Ruderer:
Approximating Prize-Collecting Variants of TSP. 7:1-7:17 - Antoine Amarilli, Corentin Barloy, Louis Jachiet, Charles Paperman:
Dynamic Membership for Regular Tree Languages. 8:1-8:18 - Antoine Amarilli, Florin Manea, Tina Ringleb, Markus L. Schmid:
Linear Time Subsequence and Supersequence Regex Matching. 9:1-9:19 - Melissa Antonelli, Arnaud Durand, Juha Kontinen:
Characterizing Small Circuit Classes from FAC⁰ to FAC¹ via Discrete Ordinary Differential Equations. 10:1-10:18 - Ivan Baburin, Matthew Cook, Florian Grötschla, Andreas Plesner, Roger Wattenhofer:
Universality Frontier for Asynchronous Cellular Automata. 11:1-11:18 - Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, Moritz Stocker:
Online Knapsack Problems with Estimates. 12:1-12:19 - Jakub Balabán, Daniel Mock, Peter Rossmanith:
Solving Partial Dominating Set and Related Problems Using Twin-Width. 13:1-13:19 - Mrudula Balachander, Emmanuel Filiot, Raffaella Gentilini, Nikos Tzevelekos:
Register Automata with Permutations. 14:1-14:18 - Júlia Baligács, Sofia Brenner, Annette Lutz, Lena Volk:
Symmetry Classes of Hamiltonian Cycles. 15:1-15:18 - Edgar Baucher, François Dross, Cyril Gavoille:
Isometric-Universal Graphs for Trees. 16:1-16:16 - Deepu Benson, Balagopal Komarath, Nikhil S. Mande, Nalli Sai Soumya, Jayalal Sarma, Karteek Sreenivasaiah:
Sensitivity and Query Complexity Under Uncertainty. 17:1-17:17 - Christoph Berkholz, Moritz Lichter, Harry Vinall-Smeeth:
Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism. 18:1-18:19 - C. S. Bhargav, Shiteng Chen, Radu Curticapean, Prateek Dwivedi:
Monotone Bounded-Depth Complexity of Homomorphism Polynomials. 19:1-19:18 - Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, Saket Saurabh:
Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components. 20:1-20:18 - Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio, Giuseppe F. Italiano:
On the Performance of Mildly Greedy Players in k-Coloring Games. 21:1-21:19 - Clotilde Bizière, Thibault Hilaire, Jérôme Leroux, Grégoire Sutre:
On the Reachability Problem for Two-Dimensional Branching VASS. 22:1-22:19 - Markus Bläser, Radu Curticapean, Julian Dörfler, Christian Ikenmeyer:
Which Graph Motif Parameters Count? 23:1-23:18 - Manuel Bodirsky, Édouard Bonnet, Zaneta Semanisinová:
Temporal Valued Constraint Satisfaction Problems. 24:1-24:19 - Manuel Bodirsky, Arno Fehm:
Polynomial-Time Tractable Problems over the p-Adic Numbers. 25:1-25:17 - Jan Bok, Jirí Fiala, Nikola Jedlicková, Jan Kratochvíl:
Computational Complexity of Covering Regular Trees. 26:1-26:19 - Prosenjit Bose, Pat Morin, Karthik Murali:
Cops and Robbers for Graphs on Surfaces with Crossings. 27:1-27:18 - Romain Bourneuf, Jana Masaríková, Wojciech Nadara, Marcin Pilipczuk:
Graphs with No Long Claws: An Improved Bound for the Analog of the Gyárfás' Path Argument. 28:1-28:16 - Olivier Bournez, Johanne Cohen, Adrian Wurm:
A Universal Uniform Approximation Theorem for Neural Networks. 29:1-29:20 - Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini:
Finding Equilibria: Simpler for Pessimists, Simplest for Optimists. 30:1-30:18 - Véronique Bruyère, Christophe Grandmont, Jean-François Raskin:
Games with ω-Automatic Preference Relations. 31:1-31:19 - Vuong Bui, Matthieu Rosenfeld:
A Proof of Shur's Conjecture on the Growth of Power-Free Languages over Large Alphabets. 32:1-32:8 - Jean Cardinal, Xavier Goaoc, Sarah Wajsbrot:
Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization. 33:1-33:18 - Balder ten Cate, Phokion G. Kolaitis, Arnar Á. Kristjánsson:
Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts. 34:1-34:18 - Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk:
A Note on the Complexity of Defensive Domination. 35:1-35:15 - Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Wiktor Zuba:
Counting Distinct Square Substrings in Sublinear Time. 36:1-36:19 - Dror Chawin, Ishay Haviv:
New Hardness Results for Low-Rank Matrix Completion. 37:1-37:18 - Elias Rojas Collins, Chris Köcher, Georg Zetzsche:
The Complexity of Separability for Semilinear Sets and Parikh Automata. 38:1-38:21 - Anupam Das, Abhishek De:
Right-Linear Lattices: An Algebraic Theory of ω-Regular Languages, with Fixed Points. 39:1-39:17 - Anuj Dawar, Erich Grädel, Leon Kullmann, Benedikt Pago:
Symmetric Proofs in the Ideal Proof System. 40:1-40:18 - Jona Dirks, Alexandre Vigny:
Token Sliding Reconfiguration on DAGs. 41:1-41:17 - Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, Daniel Vaz:
Broadcasting Under Structural Restrictions. 42:1-42:18 - Fabian Egidy, Christian Glaßer, Fynn Godau:
The Complexity of Computing Second Solutions. 43:1-43:16 - Leah Epstein, Asaf Levin:
An EPTAS for Minimizing the Total Weighted Completion Time of Jobs with Release Dates on Uniformly Related Machines. 44:1-44:18 - Javier Esparza, Valentin Krasotin:
Regular Model Checking for Systems with Effectively Regular Reachability Relation. 45:1-45:19 - Sándor P. Fekete, Kai Kobbe, Dominik Krupke, Joseph S. B. Mitchell, Christian Rieck, Christian Scheffer:
Guarding Offices with Maximum Dispersion. 46:1-46:17 - Florent Ferrari, Emmanuel Hainry, Romain Péchoux, Mário Silva:
Quantum Programming in Polylogarithmic Time. 47:1-47:17 - Gabriele Fici, Estéban Gabory:
Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform. 48:1-48:18 - Gabriele Fici, Giuseppe Romana, Marinella Sciortino, Cristian Urbina:
Morphisms and BWT-Run Sensitivity. 49:1-49:18 - Emmanuel Filiot, Nathan Lhote, Pierre-Alain Reynier:
Lexicographic Transductions of Finite Words. 50:1-50:18 - Xiaoyang Gong, Bakh Khoussainov, Yuyang Zhuge:
Word Structures and Their Automatic Presentations. 51:1-51:18 - Christoph Grüne, Lasse Wulf:
On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy. 52:1-52:18 - Lucie Guillou, Arnaud Sangnier, Nathalie Sznajder:
Wait-Only Broadcast Protocols Are Easier to Verify. 53:1-53:17 - Rohit Gurjar, Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi:
Quasipolynomial-Time Deterministic Kernelization and (Gammoid) Representation. 54:1-54:17 - Hashimoto Go, Daniel Gaina:
Model-Theoretic Forcing in Transition Algebra. 55:1-55:18 - Vojtech Havlena, Michal Hecko, Lukás Holík, Ondrej Lengál:
Negated String Containment Is Decidable. 56:1-56:20 - Thomas A. Henzinger, Aditya Prakash, K. S. Thejaswini:
Resolving Nondeterminism with Randomness. 57:1-57:18 - John M. Hitchcock, Adewale Sekoni, Hadi Shafei:
Random Permutations in Computational Complexity. 58:1-58:17 - Petr Hlinený:
Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs. 59:1-59:17 - Lukasz Kaminski, Slawomir Lasota:
Reachability in Symmetric VASS. 60:1-60:17 - Amin Karamlou:
Quantum Relaxations of CSP and Structure Isomorphism. 61:1-61:18 - Stefan Kiefer, Andrew Ryzhikov:
The Complexity of Reachability Problems in Strongly Connected Finite Automata. 62:1-62:19 - Yael Kirkpatrick, Virginia Vassilevska Williams:
Shortest Paths in Multimode Graphs. 63:1-63:16 - Orna Kupferman, Noam Shenwald:
Positional-Player Games. 64:1-64:19 - Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, Daniel Vaz:
Parameterized Spanning Tree Congestion. 65:1-65:20 - Zihui Liang, Bakh Khoussainov, Mingyu Xiao:
Deciding Regular Games: a Playground for Exponential Time Algorithms. 66:1-66:18 - Nutan Limaye, Adarsh Srinivasan, Srikanth Srinivasan:
#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank. 67:1-67:18 - Gabriele Lobbia, Wojciech Rozowski, Ralph Sarkis, Fabio Zanasi:
Quantitative Monoidal Algebra: Axiomatising Distance with String Diagrams. 68:1-68:21 - Markus Lohrey, Sebastian Maneth, Markus L. Schmid:
FO-Query Enumeration over SLP-Compressed Structures of Bounded Degree. 69:1-69:20 - Aliaume Lopez:
Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width. 70:1-70:17 - Florian Luca, Joël Ouaknine, James Worrell:
On Large Zeros of Linear Recurrence Sequences. 71:1-71:11 - Alessio Mansutti, Mikhail R. Starchak:
One-Parametric Presburger Arithmetic Has Quantifier Elimination. 72:1-72:18 - Bodo Manthey, Jesse van Rhijn:
Counting Locally Optimal Tours in the TSP. 73:1-73:17 - Malory Marin, Rémi Watrigant:
Subcoloring of (Unit) Disk Graphs. 74:1-74:17 - George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis:
Temporal Graph Realization with Bounded Stretch. 75:1-75:19 - Éléanore Meyer, Jürgen Giesl:
Deciding Termination of Simple Randomized Loops. 76:1-76:19 - Jakub Michaliszyn, Jan Otop:
Minimization of Deterministic Finite Automata Modulo the Edit Distance. 77:1-77:17 - Anand Kumar Narayanan:
Strong Keys for Tensor Isomorphism Cryptography. 78:1-78:18 - Eike Neumann:
Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space. 79:1-79:20 - Joris Nieuwveld, Joël Ouaknine:
On Expansions of Monadic Second-Order Logic with Dynamical Predicates. 80:1-80:17 - Taisei Nogami, Tachio Terauchi:
Efficient Matching of Some Fundamental Regular Expressions with Backreferences. 81:1-81:19 - Zeev Nutov:
Tight Analysis of the Primal-Dual Method for Edge-Covering Pliable Set Families. 82:1-82:14 - Michael Pinsker, Jakub Rydval, Moritz Schöbi, Christoph Spiess:
Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction. 83:1-83:20 - Andrei E. Romashchenko:
Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings. 84:1-84:18 - Neil J. Ross, Scott Wesley:
Cutoff Theorems for the Equivalence of Parameterized Quantum Circuits. 85:1-85:19 - Günter Rote:
Probabilistic Finite Automaton Emptiness Is Undecidable for a Fixed Automaton. 86:1-86:18 - Casper Moldrup Rysgaard, Sebastian Wild:
Lazy B-Trees. 87:1-87:19 - Benjamin Scheidt, Nicole Schweikardt:
Color Refinement for Relational Structures. 88:1-88:19 - Georg Schindling:
Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification. 89:1-89:19 - Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny:
Elimination Distance to Dominated Clusters. 90:1-90:20 - Ivan Titov:
Relative Randomness and Continuous Translation Functions. 91:1-91:17 - Anton Varonka, Kazuki Watanabe:
On Piecewise Affine Reachability with Bellman Operators. 92:1-92:18 - Jingyang Zhao, Mingyu Xiao:
Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity. 93:1-93: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-12-14 23:18 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:
