Portal - MFCS 2017

MFCS 2017	August 21-25, 2017 - Aalborg, Denmark
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin (Eds.)
ISBN 978-3-95977-046-0, LIPICS Vol. 83	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 39 MB)
Search Publication Server

Authors

Anglès d'Auriac, Paul-Elliot

Bergougnoux, Benjamin

Blanché, Alexandre

Bliznets, Ivan

Bodlaender, Hans L.

Boissonnat, Jean-Daniel

Chatterjee, Krishnendu

D'Angelo, Gianlorenzo

Hansen, Kristoffer Arnsfelt

Krishna, Shankara Narayanan

Nordvall Forsberg, Fredrik

Raskin, Jean-Francois

Schnoebelen, Philippe

Thilikos, Dimitrios M.

van Leeuwen, Erik Jan

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Larsen, Kim G. ; Bodlaender, Hans L. ; Raskin, Jean-Francois

Abstract | Document (358 KB) | BibTeX

Does Looking Inside a Circuit Help?

Authors: Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina ; McKenzie, Pierre ; Romani, Shadab

Abstract | Document (495 KB) | BibTeX

The Power of Programs over Monoids in DA

Authors: Grosshans, Nathan ; McKenzie, Pierre ; Segoufin, Luc

Abstract | Document (541 KB) | BibTeX

Regular Language Distance and Entropy

Authors: Parker, Austin J. ; Yancey, Kelly B. ; Yancey, Matthew P.

Abstract | Document (654 KB) | BibTeX

The Complexity of Boolean Surjective General-Valued CSPs

Authors: Fulla, Peter ; Zivny, Stanislav

Abstract | Document (527 KB) | BibTeX

On the Expressive Power of Quasiperiodic SFT

Authors: Durand, Bruno ; Romashchenko, Andrei

Abstract | Document (482 KB) | BibTeX

Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters

Authors: Bliznets, Ivan ; Karpov, Nikolai

Abstract | Document (489 KB) | BibTeX

Hypercube LSH for Approximate near Neighbors

Authors: Laarhoven, Thijs

Abstract | Document (650 KB) | BibTeX

Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems

Authors: Kawachi, Akinori ; Ogihara, Mitsunori ; Uchizawa, Kei

Abstract | Document (461 KB) | BibTeX

Dividing Splittable Goods Evenly and With Limited Fragmentation

Authors: Damaschke, Peter

Abstract | Document (421 KB) | BibTeX

Small-Space LCE Data Structure with Constant-Time Queries

Authors: Tanimura, Yuka ; Nishimoto, Takaaki ; Bannai, Hideo ; Inenaga, Shunsuke ; Takeda, Masayuki

Abstract | Document (703 KB) | BibTeX

ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics

Authors: Jeandel, Emmanuel ; Perdrix, Simon ; Vilmart, Renaud ; Wang, Quanlong

Abstract | Document (572 KB) | BibTeX

Counting Problems for Parikh Images

Authors: Haase, Christoph ; Kiefer, Stefan ; Lohrey, Markus

Abstract | Document (523 KB) | BibTeX

Communication Complexity of Pairs of Graph Families with Applications

Authors: Kolay, Sudeshna ; Panolan, Fahad ; Saurabh, Saket

Abstract | Document (566 KB) | BibTeX

Monitor Logics for Quantitative Monitor Automata

Authors: Paul, Erik

Abstract | Document (484 KB) | BibTeX

The Complexity of Quantum Disjointness

Authors: Klauck, Hartmut

Abstract | Document (432 KB) | BibTeX

Smoothed and Average-Case Approximation Ratios of Mechanisms: Beyond the Worst-Case Analysis

Authors: Deng, Xiaotie ; Gao, Yansong ; Zhang, Jie

Abstract | Document (547 KB) | BibTeX

Time Complexity of Constraint Satisfaction via Universal Algebra

Authors: Jonsson, Peter ; Lagerkvist, Victor ; Roy, Biman

Abstract | Document (578 KB) | BibTeX

The Hardness of Solving Simple Word Equations

Authors: Day, Joel D. ; Manea, Florin ; Nowotka, Dirk

Abstract | Document (640 KB) | BibTeX

Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices

Authors: Daviaud, Laure ; Guillon, Pierre ; Merlet, Glenn

Abstract | Document (530 KB) | BibTeX

Binary Search in Graphs Revisited

Authors: Deligkas, Argyrios ; Mertzios, George B. ; Spirakis, Paul G.

Abstract | Document (468 KB) | BibTeX

A Formal Semantics of Influence in Bayesian Reasoning

Authors: Jacobs, Bart ; Zanasi, Fabio

Abstract | Document (520 KB) | BibTeX

The Complexity of SORE-definability Problems

Authors: Lu, Ping ; Wu, Zhilin ; Chen, Haiming

Abstract | Document (619 KB) | BibTeX

TC^0 Circuits for Algorithmic Problems in Nilpotent Groups

Authors: Myasnikov, Alexei ; Weiß, Armin

Abstract | Document (478 KB) | BibTeX

Better Complexity Bounds for Cost Register Automata

Authors: Allender, Eric ; Krebs, Andreas ; McKenzie, Pierre

Abstract | Document (530 KB) | BibTeX

Kernelization of the Subset General Position Problem in Geometry

Authors: Boissonnat, Jean-Daniel ; Dutta, Kunal ; Ghosh, Arijit ; Kolay, Sudeshna

Abstract | Document (439 KB) | BibTeX

Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs

Authors: Glinskih, Ludmila ; Itsykson, Dmitry

Abstract | Document (465 KB) | BibTeX

The Complexity of Quantified Constraints Using the Algebraic Formulation

Authors: Carvalho, Catarina ; Martin, Barnaby ; Zhuk, Dmitriy

Abstract | Document (478 KB) | BibTeX

Induced Embeddings into Hamming Graphs

Authors: Milanic, Martin ; Mursic, Peter ; Mydlarz, Marcelo

Abstract | Document (523 KB) | BibTeX

Structured Connectivity Augmentation

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Thilikos, Dimitrios M.

Abstract | Document (688 KB) | BibTeX

Combinatorial Properties and Recognition of Unit Square Visibility Graphs

Authors: Casel, Katrin ; Fernau, Henning ; Grigoriev, Alexander ; Schmid, Markus L. ; Whitesides, Sue

Abstract | Document (581 KB) | BibTeX

Weighted Operator Precedence Languages

Authors: Droste, Manfred ; Dück, Stefan ; Mandrioli, Dino ; Pradella, Matteo

Abstract | Document (578 KB) | BibTeX

Model Checking and Validity in Propositional and Modal Inclusion Logics

Authors: Hella, Lauri ; Kuusisto, Antti ; Meier, Arne ; Virtema, Jonni

Abstract | Document (509 KB) | BibTeX

Emptiness Problems for Integer Circuits

Authors: Barth, Dominik ; Beck, Moritz ; Dose, Titus ; Glaßer, Christian ; Michler, Larissa ; Technau, Marc

Abstract | Document (499 KB) | BibTeX

Another Characterization of the Higher K-Trivials

Authors: Anglès d'Auriac, Paul-Elliot ; Monin, Benoit

Abstract | Document (499 KB) | BibTeX

The Quantum Monad on Relational Structures

Authors: Abramsky, Samson ; Barbosa, Rui Soares ; de Silva, Nadish ; Zapata, Octavio

Abstract | Document (588 KB) | BibTeX

Towards a Polynomial Kernel for Directed Feedback Vertex Set

Authors: Bergougnoux, Benjamin ; Eiben, Eduard ; Ganian, Robert ; Ordyniak, Sebastian ; Ramanujan, M. S.

Abstract | Document (517 KB) | BibTeX

Timed Network Games

Authors: Avni, Guy ; Guha, Shibashis ; Kupferman, Orna

Abstract | Document (488 KB) | BibTeX

Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings

Authors: Arvind, Vikraman ; Datta, Rajit ; Mukhopadhyay, Partha ; Raja, S.

Abstract | Document (508 KB) | BibTeX

Faster Algorithms for Mean-Payoff Parity Games

Authors: Chatterjee, Krishnendu ; Henzinger, Monika ; Svozil, Alexander

Abstract | Document (596 KB) | BibTeX

Attainable Values of Reset Thresholds

Authors: Dzyga, Michalina ; Ferens, Robert ; Gusev, Vladimir V. ; Szykula, Marek

Abstract | Document (539 KB) | BibTeX

Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees

Authors: Lagarde, Guillaume ; Limaye, Nutan ; Srinivasan, Srikanth

Abstract | Document (563 KB) | BibTeX

Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking

Authors: Pilipczuk, Michal ; van Leeuwen, Erik Jan ; Wiese, Andreas

Abstract | Document (581 KB) | BibTeX

Eilenberg Theorems for Free

Authors: Urbat, Henning ; Adámek, Jiri ; Chen, Liang-Ting ; Milius, Stefan

Abstract | Document (584 KB) | BibTeX

Membership Problem in GL(2, Z) Extended by Singular Matrices

Authors: Potapov, Igor ; Semukhin, Pavel

Abstract | Document (501 KB) | BibTeX

Grammars for Indentation-Sensitive Parsing

Authors: Nestra, Härmel

Abstract | Document (509 KB) | BibTeX

The Power of Linear-Time Data Reduction for Maximum Matching

Authors: Mertzios, George B. ; Nichterlein, André ; Niedermeier, Rolf

Abstract | Document (621 KB) | BibTeX

Two-Planar Graphs Are Quasiplanar

Authors: Hoffmann, Michael ; Tóth, Csaba D.

Abstract | Document (806 KB) | BibTeX

The Shortest Identities for Max-Plus Automata with Two States

Authors: Daviaud, Laure ; Johnson, Marianne

Abstract | Document (466 KB) | BibTeX

On the Upward/Downward Closures of Petri Nets

Authors: Atig, Mohamed Faouzi ; Meyer, Roland ; Muskalla, Sebastian ; Saivasan, Prakash

Abstract | Document (528 KB) | BibTeX

On Multidimensional and Monotone k-SUM

Authors: Hsu, Chloe Ching-Yun ; Umans, Chris

Abstract | Document (504 KB) | BibTeX

Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters

Authors: Hatanaka, Tatsuhiko ; Ito, Takehiro ; Zhou, Xiao

Abstract | Document (2,671 KB) | BibTeX

Automata in the Category of Glued Vector Spaces

Authors: Colcombet, Thomas ; Petrisan, Daniela

Abstract | Document (604 KB) | BibTeX

The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable

Authors: Paul, Erik

Abstract | Document (526 KB) | BibTeX

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems

Authors: Allender, Eric ; Hirahara, Shuichi

Abstract | Document (555 KB) | BibTeX

Strategy Complexity of Concurrent Safety Games

Authors: Chatterjee, Krishnendu ; Hansen, Kristoffer Arnsfelt ; Ibsen-Jensen, Rasmus

Abstract | Document (537 KB) | BibTeX

A Characterisation of Pi^0_2 Regular Tree Languages

Authors: Cavallari, Filippo ; Michalewski, Henryk ; Skrzypczak, Michal

Abstract | Document (570 KB) | BibTeX

On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

Authors: Dey, Palash ; Misra, Neeldhara

Abstract | Document (556 KB) | BibTeX

Fractal Intersections and Products via Algorithmic Dimension

Authors: Lutz, Neil

Abstract | Document (508 KB) | BibTeX

Domains for Higher-Order Games

Authors: Hague, Matthew ; Meyer, Roland ; Muskalla, Sebastian

Abstract | Document (532 KB) | BibTeX

Fine-Grained Complexity of Rainbow Coloring and its Variants

Authors: Agrawal, Akanksha

Abstract | Document (521 KB) | BibTeX

Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs

Authors: Chatterjee, Krishnendu ; Ibsen-Jensen, Rasmus ; Nowak, Martin A.

Abstract | Document (523 KB) | BibTeX

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis

Authors: Yamakami, Tomoyuki

Abstract | Document (488 KB) | BibTeX

Variations on Inductive-Recursive Definitions

Authors: Ghani, Neil ; McBride, Conor ; Nordvall Forsberg, Fredrik ; Spahn, Stephan

Abstract | Document (468 KB) | BibTeX

One-Dimensional Logic over Trees

Authors: Kieronski, Emanuel ; Kuusisto, Antti

Abstract | Document (493 KB) | BibTeX

An Improved FPT Algorithm for the Flip Distance Problem

Authors: Li, Shaohua ; Feng, Qilong ; Meng, Xiangzhong ; Wang, Jianxin

Abstract | Document (557 KB) | BibTeX

Reversible Kleene lattices

Authors: Brunet, Paul

Abstract | Document (591 KB) | BibTeX

Lossy Kernels for Hitting Subgraphs

Authors: Eiben, Eduard ; Hermelin, Danny ; Ramanujan, M. S.

Abstract | Document (565 KB) | BibTeX

Undecidable Problems for Probabilistic Network Programming

Authors: Kahn, David M.

Abstract | Document (502 KB) | BibTeX

Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon

Authors: Vikas, Narayan

Abstract | Document (398 KB) | BibTeX

Recognizing Graphs Close to Bipartite Graphs

Authors: Bonamy, Marthe ; Dabrowski, Konrad K. ; Feghali, Carl ; Johnson, Matthew ; Paulusma, Daniël

Abstract | Document (509 KB) | BibTeX

Parameterized Algorithms and Kernels for Rainbow Matching

Authors: Gupta, Sushmita ; Roy, Sanjukta ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (572 KB) | BibTeX

Compositional Weak Metrics for Group Key Update

Authors: Lanotte, Ruggero ; Merro, Massimo ; Tini, Simone

Abstract | Document (896 KB) | BibTeX

Clique-Width for Graph Classes Closed under Complementation

Authors: Blanché, Alexandre ; Dabrowski, Konrad K. ; Johnson, Matthew ; Lozin, Vadim V. ; Paulusma, Daniël ; Zamaraev, Viktor

Abstract | Document (533 KB) | BibTeX

Computing the Maximum using (min, +) Formulas

Authors: Mahajan, Meena ; Nimbhorkar, Prajakta ; Tawari, Anuj

Abstract | Document (392 KB) | BibTeX

Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network

Authors: D'Angelo, Gianlorenzo ; Severini, Lorenzo ; Velaj, Yllka

Abstract | Document (586 KB) | BibTeX

K4-free Graphs as a Free Algebra

Authors: Cosme Llópez, Enric ; Pous, Damien

Abstract | Document (501 KB) | BibTeX

Making Metric Temporal Logic Rational

Authors: Krishna, Shankara Narayanan ; Madnani, Khushraj ; Pandya, Paritosh K.

Abstract | Document (690 KB) | BibTeX

Complexity of Restricted Variants of Skolem and Related Problems

Authors: S., Akshay ; Balaji, Nikhil ; Vyas, Nikhil

Abstract | Document (555 KB) | BibTeX

Being Even Slightly Shallow Makes Life Hard

Authors: Muzi, Irene ; O'Brien, Michael P. ; Reidl, Felix ; Sullivan, Blair D.

Abstract | Document (640 KB) | BibTeX

Walrasian Pricing in Multi-Unit Auctions

Authors: Brânzei, Simina ; Filos-Ratsikas, Aris ; Miltersen, Peter Bro ; Zeng, Yulong

Abstract | Document (523 KB) | BibTeX

Distributed Strategies Made Easy

Authors: Castellan, Simon ; Clairambault, Pierre ; Winskel, Glynn

Abstract | Document (488 KB) | BibTeX

On Definable and Recognizable Properties of Graphs of Bounded Treewidth (Invited Talk)

Authors: Pilipczuk, Michal

Abstract | Document (233 KB) | BibTeX

Hardness and Approximation of High-Dimensional Search Problems (Invited Talk)

Authors: Pagh, Rasmus

Abstract | Document (249 KB) | BibTeX

Temporal Logics for Multi-Agent Systems (Invited Talk)

Authors: Markey, Nicolas

Abstract | Document (284 KB) | BibTeX

Ideal-Based Algorithms for the Symbolic Verification of Well-Structured Systems (Invited Talk)

Authors: Schnoebelen, Philippe

Abstract | Document (345 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)