default search action
41. MFCS 2016: Kraków, Poland
- Piotr Faliszewski, Anca Muscholl, Rolf Niedermeier:
41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland. LIPIcs 58, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2016, ISBN 978-3-95977-016-3 - Front Matter, Foreword, Conference Organization, External Reviewers, Table of Contents. 0:i-0:xvi
Invited Talk
- Shai Ben-David:
How Far Are We From Having a Satisfactory Theory of Clustering? 1:1-1:1 - Mikolaj Bojanczyk:
Decidable Extensions of MSO. 2:1-2:1 - Patricia Bouyer-Decitre:
Optimal Reachability in Weighted Timed Automata and Games. 3:1-3:3 - Tobias Friedrich:
Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms. 4:1-4:3 - Virginia Vassilevska Williams:
RNA-Folding - From Hardness to Algorithms. 5:1-5:1
Regular Papers
- Manindra Agrawal, Nitin Saxena
, Shubham Sahai Srivastava
Integer Factoring Using Small Algebraic Dependencies. 6:1-6:14 - Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich:
Routing with Congestion in Acyclic Digraphs. 7:1-7:11 - S. Akshay, Patricia Bouyer, Shankara Narayanan Krishna, Lakshmi Manasa, Ashutosh Trivedi:
Stochastic Timed Games Revisited. 8:1-8:14 - Georgios Amanatidis
Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results. 9:1-9:13 - Vivek Anand T. Kallampally, Raghunath Tewari:
Trading Determinism for Time in Space Bounded Computations. 10:1-10:13 - Dana Angluin, Udi Boker, Dana Fisman
Families of DFAs as Acceptors of omega-Regular Languages. 11:1-11:14 - Itai Arad, Adam Bouland
On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems. 12:1-12:14 - Vikraman Arvind, Frank Fuhlbrück
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. 13:1-13:14 - Martijn Baartse, Klaus Meer:
Real Interactive Proofs for VPSPACE. 14:1-14:13 - Parvaneh Babari
Synchronizing Data Words for Register Automata. 15:1-15:15 - Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker:
On the Sensitivity Conjecture for Read-k Formulas. 16:1-16:14 - Nikhil Balaji
Graph Properties in Node-Query Setting: Effect of Breaking Symmetry. 17:1-17:14 - Volker Betz, Stéphane Le Roux:
Stable States of Perturbed Markov Chains. 18:1-18:14 - Markus Bläser, Vladimir Lysikov
On Degeneration of Tensors and Algebras. 19:1-19:11 - Paul S. Bonsma, Daniël Paulusma
Using Contracted Solution Graphs for Solving Reconfiguration Problems. 20:1-20:15 - Alex Bredariol Grilo, Iordanis Kerenidis, Attila Pereszlényi:
Pointer Quantum PCPs and Multi-Prover Games. 21:1-21:14 - Paul Brunet
A Formal Exploration of Nominal Kleene Algebra. 22:1-22:13 - Maurice Chandoo:
On the Implicit Graph Conjecture. 23:1-23:13 - Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop
Nested Weighted Limit-Average Automata of Bounded Width. 24:1-24:14 - Krishnendu Chatterjee, Wolfgang Dvorák, Monika Henzinger
Conditionally Optimal Algorithms for Generalized Büchi Games. 25:1-25:15 - Dimitris Chatzidimitriou, Archontia C. Giannopoulou, Spyridon Maniatis, Clément Requilé
FPT Algorithms for Plane Completion Problems. 26:1-26:13 - Yijia Chen, Jörg Flum:
Some Lower Bounds in Parameterized AC^0. 27:1-27:14 - Samir Datta
Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs. 28:1-28:12 - Matias David Lee, Erik P. de Vink:
Logical Characterization of Bisimulation for Transition Relations over Probability Distributions with Internal Actions. 29:1-29:14 - Will Dison, Eduard Einstein, Timothy R. Riley:
Ackermannian Integer Compression and the Word Problem for Hydra Groups. 30:1-30:14 - Peter Dixon, Debasis Mandal, Aduri Pavan, N. V. Vinodchandran:
A Note on the Advice Complexity of Multipass Randomized Logspace. 31:1-31:7 - Titus Dose:
Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers. 32:1-32:13 - Andre Droschinsky, Nils M. Kriege
Faster Algorithms for the Maximum Common Subtree Isomorphism Problem. 33:1-33:14 - Eduard Eiben, Robert Ganian, O-joung Kwon
A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion. 34:1-34:14 - Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, Vuong Anh Quyen:
Preprocessing Under Uncertainty: Matroid Intersection. 35:1-35:14 - Angelo Fanelli
Ride Sharing with a Vehicle of Unlimited Capacity. 36:1-36:14 - Chenglin Fan, Omrit Filtser
On the General Chain Pair Simplification Problem. 37:1-37:14 - Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets. 38:1-38:14 - Peter Fulla, Stanislav Zivný:
On Planar Valued CSPs. 39:1-39:14 - Guilhem Gamard
Determining Sets of Quasiperiods of Infinite Words. 40:1-40:13 - Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak
On the Complexity Landscape of Connected f-Factor Problems. 41:1-41:14 - Robert Ganian, Ronald de Haan, Iyad A. Kanj, Stefan Szeider
On Existential MSO and its Relation to ETH. 42:1-42:14 - Cody W. Geary
Programming Biomolecules That Fold Greedily During Transcription. 43:1-43:14 - Thibault Godin, Ines Klimann:
Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups. 44:1-44:14 - Alexander Golovnev, Alexander S. Kulikov
Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. 45:1-45:16 - Alexander Golovnev, Edward A. Hirsch, Alexander Knop
On the Limits of Gate Elimination. 46:1-46:13 - Zeyu Guo
Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. 47:1-47:14 - Vladimir V. Gusev
On Synchronizing Colorings and the Eigenvectors of Digraphs. 48:1-48:14 - Tobias Harks, Britta Peis, Daniel Schmand
Competitive Packet Routing with Priority Lists. 49:1-49:14 - Irving van Heuven van Staereling, Bart de Keijzer, Guido Schäfer:
The Ground-Set-Cost Budgeted Maximum Coverage Problem. 50:1-50:13 - Dmitry Itsykson, Alexander Okhotin
Computational and Proof Complexity of Partial String Avoidability. 51:1-51:13 - Petr Jancar
Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w.r.t. Bisimulation Equivalence. 52:1-52:13 - Jesper Jansson
Minimal Phylogenetic Supertrees and Local Consensus Trees. 53:1-53:14 - Stacey Jeffery, François Le Gall:
Quantum Communication Complexity of Distributed Set Joins. 54:1-54:13 - Dominik Kaaser, Frederik Mallmann-Trenn, Emanuele Natale
On the Voting Time of the Deterministic Majority Process. 55:1-55:15 - Frank Kammer, Dieter Kratsch, Moritz Laudahn:
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. 56:1-56:14 - Iordanis Kerenidis, Adi Rosén, Florent Urrutia:
Multi-Party Protocols, Information Complexity and Privacy. 57:1-57:16 - Takayuki Kihara
Dividing by Zero - How Bad Is It, Really?. 58:1-58:14 - Dennis Komm
Advice Complexity of the Online Induced Subgraph Problem. 59:1-59:13 - Juha Kontinen
Decidability of Predicate Logics with Team Semantics. 60:1-60:14 - Markus Krötzsch, Tomás Masopust
On the Complexity of Universality for Partially Ordered NFAs. 61:1-61:14 - Orna Kupferman, Gal Vardi:
Eulerian Paths with Regular Constraints. 62:1-62:15 - Nadia Labai, Johann A. Makowsky:
On the Exact Learnability of Graph Parameters: The Case of Partition Functions. 63:1-63:13 - Victor Lagerkvist, Biman Roy:
A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT. 64:1-64:14 - Christof Löding, Sarah Winter:
Uniformization Problems for Tree-Automatic Relations and Top-Down Tree Transducers. 65:1-65:14 - Amaldev Manuel, A. V. Sreejith:
Two-Variable Logic over Countable Linear Orderings. 66:1-66:13 - Tomás Masopust
Piecewise Testable Languages and Nondeterministic Automata. 67:1-67:14 - George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis:
Stably Computing Order Statistics with Arithmetic Population Protocols. 68:1-68:14 - Takuya Mieno
Shortest Unique Substring Queries on Run-Length Encoded Strings. 69:1-69:11 - Shay Moran, Cyrus Rashtchian:
Shattered Sets and the Hilbert Function. 70:1-70:14 - Bart M. P. Jansen, Astrid Pieterse
Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. 71:1-71:14 - Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda:
Fully Dynamic Data Structure for LCE Queries in Compressed Space. 72:1-72:15 - Reino Niskanen
Undecidability of Two-dimensional Robot Games. 73:1-73:13 - Anurag Pandey, Nitin Saxena
Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits. 74:1-74:15 - Sudeshna Kolay, Fahad Panolan
Parameterized Algorithms on Perfect Graphs for Deletion to (r, l)-Graphs. 75:1-75:13 - Simon Perdrix, Quanlong Wang:
Supplementarity is Necessary for Quantum Diagram Reasoning. 76:1-76:14 - Thomas Place, Marc Zeitoun
The Covering Problem: A Unified Approach for Investigating the Expressive Power of Logics. 77:1-77:15 - Marcin Przybylko, Michal Skrzypczak:
On the Complexity of Branching Games with Regular Conditions. 78:1-78:14 - Paola Quaglia
Symbolic Lookaheads for Bottom-up Parsing. 79:1-79:13 - Anja Rey, Jörg Rothe:
Structural Control in Weighted Voting Games. 80:1-80:15 - Matthieu Rosenfeld
Every Binary Pattern of Length Greater Than 14 Is Abelian-2-Avoidable. 81:1-81:11 - Takayuki Sakai, Kazuhisa Seto
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression. 82:1-82:16 - Martin Schuster:
Transducer-Based Rewriting Games for Active XML. 83:1-83:13 - Igor Potapov, Pavel Semukhin
Vector Reachability Problem in SL(2, Z). 84:1-84:14 - Stephan Kreutzer, Michal Pilipczuk
The Generalised Colouring Numbers on Classes of Bounded Expansion. 85:1-85:13 - Xiang Huang
Polynomial Space Randomness in Analysis. 86:1-86:13 - Kenjiro Takazawa:
Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs. 87:1-87:14 - Christof Löding, Andreas Tollkötter:
Transformation Between Regular Expressions and omega-Automata. 88:1-88:13 - Mingyu Xiao, Shaowei Kou:
An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two. 89:1-89:14
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-12-12 21:06 CET 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: