47th International Symposium on

Mathematical Foundations of Computer Science

August 22—26, 2022, Vienna, Austria

Sponsors and partners:



Accepted Papers

Martin Bullinger. Boundaries to Single-Agent Stability in Additively Separable Hedonic Games
George Kenison. On the Skolem Problem for Reversible Sequences
Mingyang Gong, Jing Fan, Guohui Lin and Eiji Miyano. Approximation algorithms for covering vertices by long paths
Ruiwen Dong. On the Identity Problem for Unitriangular Matrices of Dimension Four
Benjamin Aram Berendsohn, Simona Boyadzhiyska and Laszlo Kozma. Fixed-point cycles and approximate EFX allocations
Gaëtan Douéneau-Tabot and Olivier Carton. Continuous rational functions are deterministic regular
Mo Liu, Anantha Padmanabha, R. Ramanujam and Yanjing Wang. Generalized Bundled Fragments of First-order Modal Logic
Ishay Haviv and Michal Parnas. On the Binary and Boolean Rank of Regular Matrices
Nina Klobas, George Mertzios, Hendrik Molter and Paul Spirakis. The complexity of computing optimum labelings for temporal connectivity
Alexandre Clément and Simon Perdrix. Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus
Bartosz Bednarczyk and Reijo Jaakkola. Towards Model Theory of Ordered Logics: Expressivity and Interpolation
Patrizio Angelini, Steven Chaplick, Sabine Cornelsen and Giordano Da Lozzo. On Upward-Planar L-Drawings of Graphs
Ilario Bonacina, Nicola Galesi and Massimo Lauria. On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
Nadia Creignou, Arnaud Durand and Heribert Vollmer. Enumeration Classes Defined by Circuits
Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza and Prafullkumar Tale. Reducing the Vertex Cover Number via Edge Contractions
Jakub Michaliszyn and Jan Otop. Learning Deterministic Visibly Pushdown Automata under Accessible Stack
Gregory Emdin, Alexander Kulikov, Ivan Mihajlin and Nikita Slezkin. CNF Encodings of Parity
Niclas Boehmer, Klaus Heeger and Rolf Niedermeier. Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
Gal Beniamini. Algebraic Representations of Unique Bipartite Perfect Matching
Haitao Wang and Yiming Zhao. Computing the Minimum Bottleneck Moving Spanning Tree
Mikaël Monet and Antoine Amarilli. Weighted counting of matchings in unbounded-treewidth graph families
Markus Lohrey and Lukas Lück. Streaming word problems
Petr Gregor, Arturo Merino and Torsten Mütze. The Hamilton compression of highly symmetric graphs
Yijia Chen, Jörg Flum, Mingjun Liu and Zhiyang Xun. On Algorithms Based on Finitely Many Homomorphism Counts
Amotz Bar-Noy, David Peleg, Mor Perry and Dror Rawitz. Graph Realization of Distance Sets
Alexander Kulikov, Danila Pechenev and Nikita Slezkin. SAT-based Circuit Local Improvement
Aleksander Bjørn Grodt Christiansen Christiansen, Jacob Holm, Eva Rotenberg and Carsten Thomassen. On Dynamic α + 1 Arboricity Decomposition and Out-Orientation
David Auger, Pierre Coucheney and Loric Duhaze. Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs
Dominik Peteler and Karin Quaas. Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order
Dmitry Itsykson and Artur Riazanov. Automating OBDD proofs is NP-hard
Amotz Bar-Noy, Toni Böhnlein, David Peleg and Dror Rawitz. On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph
Duncan Adamson, Argyrios Deligkas, Vladimir Gusev and Igor Potapov. The Complexity of Periodic Energy Minimisation
Anton Ehrmanntraut, Fabian Egidy and Christian Glaßer. Oracle with P = NP ∩ coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas and Ryan Williams. On the Number of Quantifiers as a Complexity Measure
Arthur Jaquard and Thomas Colcombet. A Complexity Approach to Tree Algebras: the Polynomial Case
Alexander Rabinovich. On Uniformization in the Full Binary Tree
Seiichiro Tani. Space-Bounded Unitary Quantum Computation with Postselection
Markus Lohrey, Andreas Rosowski and Georg Zetzsche. Membership problems in finite groups
Dominik Bojko, Karol Gotfryd, Dariusz Kowalski and Dominik Pajak. Tree exploration in dual-memory model
Michel Rigo, Manon Stipulanti and Markus Whiteland. On extended boundary sequences of morphic and Sturmian words
Titouan Carette and Robert Booth. Complete ZX-calculi for the stabiliser fragment in odd prime dimensions
Panagiotis Kanellopoulos, Maria Kyropoulou and Alexandros Voudouris. Not all Strangers are the Same: The Impact of Tolerance in Schelling Games
Patrizio Angelini, Michael A. Bekos, Julia Katheder, Michael Kaufmann and Maximilian Pfister. RAC Drawings of Graphs with Bounded Degree
Jingyang Zhao, Mingyu Xiao and Chao Xu. Improved Approximation Algorithms for The Traveling Tournament Problem
Samson Abramsky and Dan Marsden. Comonadic semantics for hybrid logic
Alexandre Fernandez, Luidnel Maignan and Antoine Spicher. Non-Determinism in Lindenmayer Systems and Global Transformations
Zhuan Khye Koh and Georg Loho. Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
Aleks Kissinger and Will Simmons. Higher-order causal theories are models of BV-logic
Guido Brückner, Ignaz Rutter and Peter Stumpf. Extending Partial Representations of Circle Graphs in Near-Linear Time
Jędrzej Kołodziejski and Bartek Klin. Countdown mu-calculus
Matthew Earnshaw and Paweł Sobociński. Regular Monoidal Languages
Mingyang Deng, Virginia Vassilevska Williams and Ziqian Zhong. New Lower Bounds and Upper Bounds for Listing Avoidable Vertices
Alexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix and Benoît Valiron. LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits
Dariusz Dereniowski and Izajasz Wrosz. Constant-factor approximation algorithm for binary search in trees with monotonic query times
Lane A. Hemaspaandra, Mandar Juvekar, Arian Nadjimzadah and Patrick A. Phillips. Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
Timo Gervens and Martin Grohe. Graph Similarity Based on Matrix Norms
Yuri Bilu, Florian Luca, Joris Nieuwveld, Joel Ouaknine, David Purser and James Worrell. Skolem Meets Schanuel
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi and Kunihiro Wasa. Independent set reconfiguration on directed graphs
Severine Fratani, Guillaume Maurras and Pierre-Alain Reynier. A robust class of languages of 2-nested words
Nicolas El Maalouly and Raphael Steiner. Exact Matching in Graphs of Bounded Independence Number
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel and Yann Vaxès. Sample compression schemes for balls in graphs
Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi and Saket Saurabh. Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets
Balagopal Komarath, Anurag Pandey and Nitin Saurabh. Rabbits approximate, cows compute exactly!
Florian Luca, Joel Ouaknine and James Worrell. A Universal Skolem Set of Positive Lower Density
Tim A. Hartmann and Stefan Lendl. Dispersing Obnoxious Facilities on Graphs by Rounding Distances
Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma and Prafullkumar Tale. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram and Rogers Mathew. Conflict-free Coloring on Claw-free graphs and Interval graphs
Christian Komusiewicz and Nils Morawietz. Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard
Hoang-Oanh Le and Van Bang Le. Complexity of the Cluster Vertex Deletion problem on graphs without forbidden induced subgraphs
Julian D'Costa, Toghrul Karimov, Rupak Majumdar, Joel Ouaknine, Mahmoud Salamati and James Worrell. The Pseudo-Reachability Problem for Affine Dynamical Systems
Adam Ó Conghaile. Cohomology in Constraint Satisfaction and Structure Isomorphism
Dmitry Chistikov, Christoph Haase, Zahra Hadizadeh and Alessio Mansutti. Higher-Order Boolean Satisfiability
Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joel Ouaknine and James Worrell. Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set
Jin-Yi Cai and Daniel Szabo. Bounded Degree Nonnegative Counting CSP
C. S. Bhargav, Sagnik Dutta and Nitin Saxena. Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits
Radovan Červený, Pratibha Choudhary and Ondřej Suchý. On Kernels for d-Path Vertex Cover
M. S. Ramanujan, Abhishek Sahu, Saket Saurabh and Shaily Verma. An exact algorithm for Knot-free Vertex Deletion
S. Akshay and Supratik Chakraborty. On Synthesizing Computable Skolem Functions for First Order Logic

Contact: Stefan Szeider (mfcs2022@ac.tuwien.ac.at)