MFCS

Publications

2024

Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Pawel Rzazewski, Oliver Schaudt
Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes. MFCS (2024)
Benjamin Monmege, Julie Parreaux, Pierre-Alain Reynier
Synthesis of Robust Optimal Real-Time Systems. MFCS (2024)
Anuj Dawar, Ioannis Eleftheriadis
Preservation Theorems on Sparse Classes Revisited. MFCS (2024)
Bartlomiej Bosek, Grzegorz Gutowski, Michal Lason, Jakub Przybylo
First-Fit Coloring of Forests in Random Arrival Model. MFCS (2024)
Dariusz Kalocinski, Luca San Mauro, Michal Wroclawski
Punctual Presentability in Certain Classes of Algebraic Structures. MFCS (2024)
Guillermo Badia, Manfred Droste, Carles Noguera, Erik Paul
Logical Characterizations of Weighted Complexity Classes. MFCS (2024)
Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, Rik Sengupta
On the Number of Quantifiers Needed to Define Boolean Functions. MFCS (2024)
Shaun Azzopardi, David Lidell, Nir Piterman
A Direct Translation from LTL with Past to Deterministic Rabin Automata. MFCS (2024)
Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, Frank Sommer
On the Complexity of Community-Aware Network Sparsification. MFCS (2024)
Petr Hlinený, Jan Jedelský
ℋ-Clique-Width and a Hereditary Analogue of Product Structure. MFCS (2024)
Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, Dror Rawitz
On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper). MFCS (2024)
Markus Lohrey, Julio Xochitemol
Streaming in Graph Products. MFCS (2024)
Jesse Beisegel, Ekkehard Köhler, Fabienne Ratajczak, Robert Scheffler, Martin Strehler
Graph Search Trees and the Intermezzo Problem. MFCS (2024)
Zohair Raza Hassan
The Complexity of (P₃, H)-Arrowing and Beyond. MFCS (2024)
Dibyayan Chakraborty, Haiko Müller, Sebastian Ordyniak, Fahad Panolan, Mateusz Rychlicki
Covering and Partitioning of Split, Chain and Cographs with Isometric Paths. MFCS (2024)
Antonio Casares, Corto Mascle
The Complexity of Simplifying ω-Automata Through the Alternating Cycle Decomposition. MFCS (2024)
Michal Makowski
On the Complexity of the Conditional Independence Implication Problem with Bounded Cardinalities. MFCS (2024)
Kristóf Bérczi, Tamás Király, Daniel P. Szabo
Multiway Cuts with a Choice of Representatives. MFCS (2024)
Olaf Beyersdorff, Tim Hoffmann, Kaspar Kasche, Luc Nicolas Spachmann
Polynomial Calculus for Quantified Boolean Logic: Lower Bounds Through Circuits and Degree. MFCS (2024)
Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen
Sublinear Time Shortest Path in Expander Graphs. MFCS (2024)
Sourav Chakraborty, Swarnalipa Datta, Pranjal Dutta, Arijit Ghosh, Swagato Sanyal
On Fourier Analysis of Sparse Boolean Functions over Certain Abelian Groups. MFCS (2024)
Alexander A. Rubtsov, Nikita Chudinov
Computational Model for Parsing Expression Grammars. MFCS (2024)
Jarkko Kari
On Low Complexity Colorings of Grids (Invited Talk). MFCS (2024)
Isolde Adler, Eva Fluck
Monotonicity of the Cops and Robber Game for Bounded Depth Treewidth. MFCS (2024)
Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, Jean-Florent Raymond
Local Certification of Geometric Graph Classes. MFCS (2024)
Wiktor Zuba, Grigorios Loukides, Solon P. Pissis, Sharma V. Thankachan
Approximate Suffix-Prefix Dictionary Queries. MFCS (2024)
Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, Dror Rawitz
Sparse Graphic Degree Sequences Have Planar Realizations. MFCS (2024)
Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, Thomas Zeume
Query Maintenance Under Batch Changes with Small-Depth Circuits. MFCS (2024)
Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev
Symmetric-Difference (Degeneracy) and Signed Tree Models. MFCS (2024)
Filippo Bonchi, Alessandro Di Giorgio, Davide Trotta
When Lawvere Meets Peirce: An Equational Presentation of Boolean Hyperdoctrines. MFCS (2024)
Dhanyamol Antony, Yixin Cao, Sagartanu Pal, R. B. Sandeep
Switching Classes: Characterization and Computation. MFCS (2024)
Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter
The Freeness Problem for Automaton Semigroups. MFCS (2024)
Nathan van Beusekom, Marc J. van Kreveld, Max van Mulken, Marcel Roeloffzen, Bettina Speckmann, Jules Wulms
Capturing the Shape of a Point Set with a Line Segment. MFCS (2024)
David Dingel, Fabian Egidy, Christian Glaßer
An Oracle with no UP-Complete Sets, but NP = PSPACE. MFCS (2024)
Melissa Antonelli, Arnaud Durand, Juha Kontinen
A New Characterization of FAC⁰ via Discrete Ordinary Differential Equations. MFCS (2024)
Marta Piecyk
C_{2k+1}-Coloring of Bounded-Diameter Graphs. MFCS (2024)
Daniel Král, Kristýna Pekárková, Kenny Storgel
Twin-Width of Graphs on Surfaces. MFCS (2024)
Susobhan Bandopadhyay, Aritra Banik, Diptapriyo Majumdar, Abhishek Sahu
Tractability of Packing Vertex-Disjoint A-Paths Under Length Constraints. MFCS (2024)
Arnold Beckmann, Georg Moser
On Complexity of Confluence and Church-Rosser Proofs. MFCS (2024)
Syamantak Das, Nikhil Kumar, Daniel Vaz
Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs. MFCS (2024)
Zeno Bitter, Antoine Mottet
Generalized Completion Problems with Forbidden Tournaments. MFCS (2024)
Rupak Majumdar
Fine-Grained Complexity of Program Analysis (Invited Talk). MFCS (2024)
Arnaud Casteigts, Nils Morawietz, Petra Wolf
Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs. MFCS (2024)
Yakov Shalunov
Leakage-Resilient Hardness Equivalence to Logspace Derandomization. MFCS (2024)
Jack H. Lutz, Andrei N. Migunov
Algorithmic Dimensions via Learning Functions. MFCS (2024)
Tim Seppelt
An Algorithmic Meta Theorem for Homomorphism Indistinguishability. MFCS (2024)
Lisa-Marie Jaser, Jacobo Torán
Pebble Games and Algebraic Proof Systems. MFCS (2024)
Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor
The Canadian Traveller Problem on Outerplanar Graphs. MFCS (2024)
Avantika Agarwal, Sevag Gharibian, Venkata Koppula, Dorian Rudolph
Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds. MFCS (2024)

volume 306, 2024

49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia MFCS 306 (2024)