|
42nd International Symposium on Mathematical Foundations of Computer Science August 21-25, 2017, Aalborg (Denmark) |
MFCS-17 is organized in coopperation with EATCS |
Accepted PapersThe following papers are accepted for presentation at MFCS-2017
Does Looking Inside a Circuit Help?
The power of programs over monoids in DA
Regular Language Distance and Entropy
The complexity of Boolean surjective general-valued CSPs
On the expressive power of quasi-periodic SFT
Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
Hypercube LSH for approximate near neighbors
Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems
Dividing Splittable Goods Evenly and With Limited Fragmentation
Small-space LCE data structure with constant-time queries
ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T quantum mechanics
Counting Problems for Parikh Images
Communication Complexity of Pairs of Graph Families with Applications
Monitor Logics for Quantitative Monitor Automata
The Complexity of Quantum Disjointness
Smoothed and Average-case Approximation Ratios of Mechanisms: Beyond the Worst-case Analysis
Time Complexity of Constraint Satisfaction via Universal Algebra
The Hardness of Solving Simple Word Equations
Comparison of max-plus automata and joint spectral radius of tropical matrices
Binary Search in Graphs Revisited
A Formal Semantics of Influence in Bayesian Reasoning
The Complexity of SORE-definability Problem
TC^0 circuits for algorithmic problems in nilpotent groups
Better Complexity Bounds for Cost Register Machines
Kernelization of the Subset General Position problem in Geometry
Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
The complexity of quantified constraints using the algebraic formulation
Induced embeddings into Hamming graphs
Structured Connectivity Augmentation
Combinatorial Properties and Recognition of Unit Square Visibility Graphs
Weighted Operator Precedence Languages
Model checking and validity in propositional and modal inclusion logics
Emptiness Problems for Integer Circuits
Another characterization of the higher K-Trivials
The quantum monad on relational structures
Towards a Polynomial Kernel for Directed Feedback Vertex Set
Timed Network Games
Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings
Faster Algorithms for Mean-Payoff Parity Games
Attainable values of reset thresholds
Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees
Approximation and parameterized algorithms for geometric independent set with shrinking
Eilenberg Theorems for Free
Membership problem in GL(2,Z) extended by singular matrices
Grammars for Indentation-Sensitive Parsing
The Power of Data Reduction for Matching
Two-Planar Graphs Are Quasiplanar
The Shortest Identities for Max-Plus Automata with Two States
On the Upward/Downward Closures of Petri Nets
On Multidimensional and Monotone k-SUM
Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
Automata in the Category of Glued Vector Spaces
The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems
Strategy Complexity of Concurrent Safety Games
A characterisation of Pi^0_2 regular tree languages
On the Exact Amount of Missing Information that makes Finding Possible Winners Hard
Fractal Intersections and Products via Algorithmic Dimension
Domains for Higher-Order Games
Fine-grained Complexity of Rainbow Coloring and its Variants
Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
Variations on inductive-recursive definitions
One-Dimensional Logic over Trees
An Improved Fixed-parameterized Algorithm for Parameterized Flip Distance Problem
Reversible Kleene Lattices
Lossy Kernels for Hitting Subgraphs
Undecidable Problems for Probabilistic Network Programming
Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
Recognizing Graphs Close to Bipartite Graphs
Parameterized Algorithms and Kernels for Rainbow Matching
Compositional weak metrics for group key update
Clique-Width for Graph Classes Closed under Complementation
Computing the maximum using (min,+) formulas
Selecting nodes and buying links to maximize the information diffusion in a network
K4-free graphs as a free algebra
Making Metric Temporal Logic Rational
Complexity of restricted variants of Skolem and related problems
Being even slightly shallow makes life hard
Optimal Walrasian Pricing in Multi-unit Auctions
|
|
Contact: Giovanni Bacci |