|
45th International Symposium on Mathematical Foundations of Computer Science August 24-28, 2020, Prague (Czech Republic) |
|
Sponsors: 
MFCS 2020 is organized in cooperation with EATCS |
Accepted PapersHitting forbidden induced subgraphs on bounded treewidth graphs Classically Simulating Quantum Circuits with Local Depolarizing Noise Reducing graph transversals via edge contractions Complexity of counting first-order logic for the subword order All growth rates of abelian exponents are attained by infinite binary words Factoring polynomials over finite fields with linear Galois groups: an additive combinatorics approach VC density of set systems definable in tree-like graphs The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains Fast algorithms for general spin systems on bipartite expanders Complexity of Computing the Anti-Ramsey Numbers for Paths Layered Fan-Planar Graph Drawings Isomorphism Problem for S_d -graphs A relaxation of the Directed Disjoint Paths problem: a global congestion metric helps An Improved Approximation Algorithm for Scheduling under Arborescence Precedence Constraints Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR functions A Timecop’s Work is Harder Than You Think Regular resynchronizability of origin transducers is undecidable Preservation of Equations by Monoidal Monads Randomization in Non-Uniform Finite Automata ∃R-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games Minimum 0-Extension Problems on Directed Metrics Best Fit Bin Packing with Random Order Revisited PBS-calculus: A Graphical Language for Coherent Control of Quantum Computations Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests Dynamic time warping-based proximity problems Decidability in Group Shifts and Group Cellular Automata The complexity of approximating the complex-valued Potts model Improved Explicit Data Structures in the Bit-probe Model using Error Correcting Codes Simplified Game of Life: Algorithms and Complexity Ambiguity Hierarchy of Regular Infinite Tree Languages Synchronizing Deterministic Push-Down Automata Can Be Really Hard Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle Ideal Membership Problem and a Majority Polymorphism Over the Ternary Domain Quantum-Inspired Classical Algorithms for Singular Value Transformation A polynomial kernel for 3-leaf power deletion Regular choice functions and uniformisations for countable domains Value iteration using universal graphs and the complexity of mean payoff games Optimally Resilient Strategies in Pushdown Safety Games Randomness and effective dimension of continued fractions Efficient Enumerations for Minimal Multicuts and Multiway Cuts On Affine Reachability Problems Register transducers are marble transducers On the Parameterized Complexity of Deletion to {\cal H}-free Strong Components Knapsack and power word problems in solvable Baumslag-Solitar groups Solving Packing Problems with Few Small Items Using Rainbow Matchings Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs Analysing Spatial Properties on Neighbourhood Spaces Algorithms for the rainbow vertex coloring problem on graph classes Structural Parameterizations of Clique Coloring On Repetition Languages Some remarks on deciding equivalence for graph-to-graph transducers Fractional Covers of Hypergraphs with Bounded Multi-Intersection Computing a Minimum-Cost $k$-hop Steiner Tree in Tree-Like Metrics Building large k-cores from sparse graphs Topological Influence and Locality in Swap Schelling Games On a temporal logic of prefixes and infixes Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming The mergegram of a dendrogram and its stability Extending Nearly Complete 1-Planar Drawings in Polynomial Time Quick Separation in Chordal and Split Graphs List homomorphism problems for signed graphs Graph Clustering in All Parameter Regimes Slice rank of block tensors and irreversibility of structure tensors of algebras Approximation in (Poly)logarithmic Space U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited A Quasiorder-based Perspective on Residual Automata Unary Prime Languages Sensitivity lower bounds from linear dependencies Elimination Distance to Bounded Degree on Planar Graphs Hierarchical Clusterings of Unweighted Graphs Palindromic k-Factorization in Pure Linear Time Span programs and quantum time complexity Linear High-Order Deterministic Tree transducers with Regular look-ahead Continuous and monotone machines Even faster algorithms for CSAT over supernilpotent algebras Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems A Special Case of Rational Identity Testing and the Bre\v{s}ar-Klep Theorem Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes |