default search action
42nd MFCS 2017: Aalborg, Denmark
- Kim G. Larsen, Hans L. Bodlaender, Jean-François Raskin:
42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark. LIPIcs 83, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2017, ISBN 978-3-95977-046-0 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xvi
- Russell Impagliazzo
, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani:
Does Looking Inside a Circuit Help?. 1:1-1:13 - Nathan Grosshans
The Power of Programs over Monoids in DA. 2:1-2:20 - Austin J. Parker, Kelly B. Yancey, Matthew P. Yancey:
Regular Language Distance and Entropy. 3:1-3:14 - Peter Fulla, Stanislav Zivný:
The Complexity of Boolean Surjective General-Valued CSPs. 4:1-4:14 - Bruno Durand, Andrei E. Romashchenko
On the Expressive Power of Quasiperiodic SFT. 5:1-5:14 - Ivan Bliznets
Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters. 6:1-6:14 - Thijs Laarhoven
Hypercube LSH for Approximate near Neighbors. 7:1-7:20 - Akinori Kawachi, Mitsunori Ogihara
Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems. 8:1-8:13 - Peter Damaschke:
Dividing Splittable Goods Evenly and With Limited Fragmentation. 9:1-9:13 - Yuka Tanimura, Takaaki Nishimoto, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda:
Small-Space LCE Data Structure with Constant-Time Queries. 10:1-10:15 - Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart, Quanlong Wang:
ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics. 11:1-11:13 - Christoph Haase
Counting Problems for Parikh Images. 12:1-12:13 - Sudeshna Kolay, Fahad Panolan
Communication Complexity of Pairs of Graph Families with Applications. 13:1-13:13 - Erik Paul:
Monitor Logics for Quantitative Monitor Automata. 14:1-14:13 - Hartmut Klauck
The Complexity of Quantum Disjointness. 15:1-15:13 - Xiaotie Deng
Smoothed and Average-Case Approximation Ratios of Mechanisms: Beyond the Worst-Case Analysis. 16:1-16:15 - Peter Jonsson, Victor Lagerkvist, Biman Roy:
Time Complexity of Constraint Satisfaction via Universal Algebra. 17:1-17:15 - Joel D. Day, Florin Manea, Dirk Nowotka:
The Hardness of Solving Simple Word Equations. 18:1-18:14 - Laure Daviaud
Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices. 19:1-19:14 - Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis:
Binary Search in Graphs Revisited. 20:1-20:14 - Bart Jacobs, Fabio Zanasi
A Formal Semantics of Influence in Bayesian Reasoning. 21:1-21:14 - Ping Lu, Zhilin Wu, Haiming Chen:
The Complexity of SORE-definability Problems. 22:1-22:15 - Alexei G. Myasnikov, Armin Weiß
TC0 Circuits for Algorithmic Problems in Nilpotent Groups. 23:1-23:14 - Eric Allender
Better Complexity Bounds for Cost Register Automata. 24:1-24:14 - Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh, Sudeshna Kolay:
Kernelization of the Subset General Position Problem in Geometry. 25:1-25:13 - Ludmila Glinskih, Dmitry Itsykson:
Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs. 26:1-26:12 - Catarina Carvalho
The Complexity of Quantified Constraints Using the Algebraic Formulation. 27:1-27:14 - Martin Milanic, Peter Mursic
Induced Embeddings into Hamming Graphs. 28:1-28:15 - Fedor V. Fomin
Structured Connectivity Augmentation. 29:1-29:13 - Katrin Casel, Henning Fernau
Combinatorial Properties and Recognition of Unit Square Visibility Graphs. 30:1-30:15 - Manfred Droste, Stefan Dück, Dino Mandrioli, Matteo Pradella
Weighted Operator Precedence Languages. 31:1-31:15 - Lauri Hella
Model Checking and Validity in Propositional and Modal Inclusion Logics. 32:1-32:14 - Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau
Emptiness Problems for Integer Circuits. 33:1-33:14 - Paul-Elliot Anglès d'Auriac, Benoît Monin:
Another Characterization of the Higher K-Trivials. 34:1-34:13 - Samson Abramsky
The Quantum Monad on Relational Structures. 35:1-35:19 - Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak
Towards a Polynomial Kernel for Directed Feedback Vertex Set. 36:1-36:15 - Guy Avni, Shibashis Guha, Orna Kupferman:
Timed Network Games. 37:1-37:16 - Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, S. Raja:
Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings. 38:1-38:13 - Krishnendu Chatterjee
Faster Algorithms for Mean-Payoff Parity Games. 39:1-39:14 - Michalina Dzyga, Robert Ferens
Attainable Values of Reset Thresholds. 40:1-40:14 - Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan
Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees. 41:1-41:14 - Michal Pilipczuk
Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking. 42:1-42:13 - Henning Urbat, Jirí Adámek, Liang-Ting Chen
Eilenberg Theorems for Free. 43:1-43:15 - Igor Potapov, Pavel Semukhin:
Membership Problem in GL(2, Z) Extended by Singular Matrices. 44:1-44:13 - Härmel Nestra:
Grammars for Indentation-Sensitive Parsing. 45:1-45:13 - George B. Mertzios, André Nichterlein, Rolf Niedermeier:
The Power of Linear-Time Data Reduction for Maximum Matching. 46:1-46:14 - Michael Hoffmann, Csaba D. Tóth:
Two-Planar Graphs Are Quasiplanar. 47:1-47:14 - Laure Daviaud
The Shortest Identities for Max-Plus Automata with Two States. 48:1-48:13 - Mohamed Faouzi Atig, Roland Meyer, Sebastian Muskalla
On the Upward/Downward Closures of Petri Nets. 49:1-49:14 - Chloe Ching-Yun Hsu, Chris Umans:
On Multidimensional and Monotone k-SUM. 50:1-50:13 - Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou:
Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters. 51:1-51:13 - Thomas Colcombet, Daniela Petrisan:
Automata in the Category of Glued Vector Spaces. 52:1-52:14 - Erik Paul:
The Equivalence, Unambiguity and Sequentiality Problems of Finitely Ambiguous Max-Plus Tree Automata are Decidable. 53:1-53:13 - Eric Allender
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. 54:1-54:14 - Krishnendu Chatterjee
Strategy Complexity of Concurrent Safety Games. 55:1-55:13 - Filippo Cavallari, Henryk Michalewski, Michal Skrzypczak:
A Characterisation of Pi^0_2 Regular Tree Languages. 56:1-56:14 - Palash Dey, Neeldhara Misra:
On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard. 57:1-57:14 - Neil Lutz:
Fractal Intersections and Products via Algorithmic Dimension. 58:1-58:12 - Matthew Hague
Domains for Higher-Order Games. 59:1-59:15 - Akanksha Agrawal
Fine-Grained Complexity of Rainbow Coloring and its Variants. 60:1-60:14 - Krishnendu Chatterjee
Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs. 61:1-61:13 - Tomoyuki Yamakami:
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis. 62:1-62:14 - Neil Ghani, Conor McBride
Variations on Inductive-Recursive Definitions. 63:1-63:13 - Emanuel Kieronski
One-Dimensional Logic over Trees. 64:1-64:13 - Shaohua Li
An Improved FPT Algorithm for the Flip Distance Problem. 65:1-65:13 - Paul Brunet
Reversible Kleene lattices. 66:1-66:14 - Eduard Eiben, Danny Hermelin, M. S. Ramanujan:
Lossy Kernels for Hitting Subgraphs. 67:1-67:14 - David M. Kahn:
Undecidable Problems for Probabilistic Network Programming. 68:1-68:17 - Narayan Vikas:
Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon. 69:1-69:14 - Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson
Recognizing Graphs Close to Bipartite Graphs. 70:1-70:14 - Sushmita Gupta, Sanjukta Roy
Parameterized Algorithms and Kernels for Rainbow Matching. 71:1-71:13 - Ruggero Lanotte
Compositional Weak Metrics for Group Key Update. 72:1-72:16 - Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson
Clique-Width for Graph Classes Closed under Complementation. 73:1-73:14 - Meena Mahajan
Computing the Maximum using (min, +) Formulas. 74:1-74:11 - Gianlorenzo D'Angelo
Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network. 75:1-75:14 - Enric Cosme-Llópez
K4-free Graphs as a Free Algebra. 76:1-76:14 - Shankara Narayanan Krishna, Khushraj Madnani
Making Metric Temporal Logic Rational. 77:1-77:14 - S. Akshay, Nikhil Balaji
Complexity of Restricted Variants of Skolem and Related Problems. 78:1-78:14 - Irene Muzi, Michael P. O'Brien, Felix Reidl
Being Even Slightly Shallow Makes Life Hard. 79:1-79:13 - Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, Yulong Zeng:
Walrasian Pricing in Multi-Unit Auctions. 80:1-80:14 - Simon Castellan, Pierre Clairambault, Glynn Winskel:
Distributed Strategies Made Easy. 81:1-81:13 - Michal Pilipczuk
On Definable and Recognizable Properties of Graphs of Bounded Treewidth (Invited Talk). 82:1-82:2 - Rasmus Pagh:
Hardness and Approximation of High-Dimensional Search Problems (Invited Talk). 83:1-83:1 - Nicolas Markey:
Temporal Logics for Multi-Agent Systems (Invited Talk). 84:1-84:3 - Philippe Schnoebelen:
Ideal-Based Algorithms for the Symbolic Verification of Well-Structured Systems (Invited Talk). 85:1-85:4
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-09-29 00:11 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: