|
47th International Symposium on Mathematical Foundations of Computer Science August 22—26, 2022, Vienna, Austria |
|
Sponsors and partners: 
|
Accepted PapersBoundaries to Single-Agent Stability in Additively Separable Hedonic Games On the Skolem Problem for Reversible Sequences Approximation algorithms for covering vertices by long paths On the Identity Problem for Unitriangular Matrices of Dimension Four Fixed-point cycles and approximate EFX allocations Continuous rational functions are deterministic regular Generalized Bundled Fragments of First-order Modal Logic On the Binary and Boolean Rank of Regular Matrices The complexity of computing optimum labelings for temporal connectivity Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus Towards Model Theory of Ordered Logics: Expressivity and Interpolation On Upward-Planar L-Drawings of Graphs On vanishing sums of roots of unity in polynomial calculus and sum-of-squares Enumeration Classes Defined by Circuits Reducing the Vertex Cover Number via Edge Contractions Learning Deterministic Visibly Pushdown Automata under Accessible Stack CNF Encodings of Parity Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems Algebraic Representations of Unique Bipartite Perfect Matching Computing the Minimum Bottleneck Moving Spanning Tree Weighted counting of matchings in unbounded-treewidth graph families Streaming word problems The Hamilton compression of highly symmetric graphs On Algorithms Based on Finitely Many Homomorphism Counts Graph Realization of Distance Sets SAT-based Circuit Local Improvement On Dynamic α + 1 Arboricity Decomposition and Out-Orientation Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order Automating OBDD proofs is NP-hard On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph The Complexity of Periodic Energy Minimisation Oracle with P = NP ∩ coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP On the Number of Quantifiers as a Complexity Measure A Complexity Approach to Tree Algebras: the Polynomial Case On Uniformization in the Full Binary Tree Space-Bounded Unitary Quantum Computation with Postselection Membership problems in finite groups Tree exploration in dual-memory model On extended boundary sequences of morphic and Sturmian words Complete ZX-calculi for the stabiliser fragment in odd prime dimensions Not all Strangers are the Same: The Impact of Tolerance in Schelling Games RAC Drawings of Graphs with Low Degree Improved Approximation Algorithms for The Traveling Tournament Problem Comonadic semantics for hybrid logic Non-Determinism in Lindenmayer Systems and Global Transformations Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees Higher-order causal theories are models of BV-logic Extending Partial Representations of Circle Graphs in Near-Linear Time Countdown mu-calculus Regular Monoidal Languages New Lower Bounds and Upper Bounds for Listing Avoidable Vertices LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits Constant-factor approximation algorithm for binary search in trees with monotonic query times Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting Graph Similarity Based on Matrix Norms Skolem Meets Schanuel Independent set reconfiguration on directed graphs A robust class of languages of 2-nested words Exact Matching in Graphs of Bounded Independence Number Sample compression schemes for balls in graphs Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets Rabbits approximate, cows compute exactly! A Universal Skolem Set of Positive Lower Density Dispersing Obnoxious Facilities on Graphs by Rounding Distances Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters Conflict-free Coloring on Claw-free graphs and Interval graphs Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard Complexity of the Cluster Vertex Deletion problem on H-free graphs The Pseudo-Reachability Problem for Affine Dynamical Systems Cohomology in Constraint Satisfaction and Structure Isomorphism Higher-Order Boolean Satisfiability Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set Bounded Degree Nonnegative Counting CSP Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits On Kernels for d-Path Vertex Cover An exact algorithm for Knot-free Vertex Deletion On Synthesizing Computable Skolem Functions for First Order Logic
|