Important Dates

Full papers: April 15, 2011
Notification: May 30, 2011
Final version: June 13, 2011
Conference: August 22-26, 2011


MFCS 2011 PC chairs:
Filip Murlak & Piotr Sankowski

Online proceedings

The online version of the proceedings is now available.

MFCS 2011 Accepted Papers

  • Dietrich Kuske and Thomas Weidner. Size and computation of injective tree automatic presentations
  • Peter Franek, Stefan Ratschan and Piotr Zgliczynski. Satisfiability of Systems of Equations of Real Analytic Functions is  Quasi-decidable
  • Markus Lohrey. Compressed word problems for inverse monoids
  • Yoram Bachrach. The Least-Core of Threshold Network Flow Games
  • Riccardo Dondi, Giancarlo Mauri and Italo Zoppis. On the Complexity of the l-diversity Problem
  • Kévin Perrot and Eric Rémila. Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence.
  • Ocan Sankur. Untimed Language Preservation in Timed Systems
  • Pawel Gawrychowski, Artur Jeż and Andreas Maletti. On minimising automata with errors
  • Evgeny Demenkov and Alexander Kulikov. An Elementary Proof of a 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
  • Olivier Bournez, Daniel Graça and Amaury Pouly. Solving Analytic Differential Equations in Polynomial Time over  Unbounded Domains
  • Vladimir Kolmogorov. Submodularity on a tree: Unifying L-convex and bisubmodular functions
  • Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: a logical approach
  • Christophe Paul, Stéphan Thomassé and Anthony Perez. Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and related problems
  • Alessandro Facchini and Balder Ten Cate. Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs
  • Stanislav Böhm and Stefan Göller. Language equivalence of deterministic real-time one-counter automata is NL-complete
  • Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas and Heribert Vollmer. Verifying Proofs in Constant Depth
  • Krishnendu Chatterjee and Laurent Doyen. Energy and Mean-Payoff Parity Markov Decision Processes
  • David A. Cohen, Paidi Creed, Peter G. Jeavons and Stanislav Zivny. An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
  • Christina Boucher. The Bounded Search Tree Algorithm for the Closest String Problem has Quadratic Smoothed Complexity
  • Marats Golovkins, Maksim Kravtsev and Vasilijs Kravcevs. Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
  • Jianxin Wang, Yongjie Yang, Jiong Guo and Jianer Chen. Linear Problem Kernels for Planar Graph Problems with Small Distance Property
  • Andrej Bogdanov, Akinori Kawachi and Hidetoki Tanaka. Hard Functions for Low-degree Polynomials over Prime Fields
  • Mingyu Xiao, Ton Kloks and Sheung-Hung Poon. New Parameterized Algorithms for Edge Dominating Set
  • Kei Uchizawa and Eiji Takimoto. Lower Bounds for Linear Decision Trees via An Energy Complexity Argument
  • Florin Manea, Robert Mercas and Catalin Tiseanu. Periodicity Algorithms for Partial Words
  • Andreas Maletti and Daniel Quernheim. Pushing for weighted tree automata
  • Markus Blaeser and Radu Curticapean. The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree
  • Jacek Chrząszcz and Aleksy Schubert. The role of polymorphism in the characterisation of complexity by soft types
  • Alexander Okhotin and Kai Salomaa. State complexity of operations on input-driven pushdown automata
  • Robert Bredereck, André Nichterlein, Rolf Niedermeier and Geevarghese Philip. Pattern-Guided Data Anonymization and Clustering
  • John Fearnley and Oded Lachish. Parity Games On Graphs With Medium Tree-width
  • Michael Vanden Boom. Weak Cost Monadic Logic Over Infinite Trees
  • Bernd Puchala and Wladimir Fridman. Distributed Synthesis for Regular and Contextfree Specifications
  • Jun Hosoda, Juraj Hromkovic, Taisuke Izumi, Hirotaka Ono, Monika Steinová and Koichi Wada. On the Approximability of Minimum Topic Connected Overlay and Its Special Instances
  • Andreas Krebs, Nutan Limaye and Srikanth Srinivasan. Streaming algorithms for recognizing nearly well-parenthesized expressions
  • Petr Golovach, Marcin Kaminski and Daniel Paulusma. Contracting a chordal graph to a split graph or a tree
  • Thomas Colcombet, Clemens Ley and Gabriele Puppis. On the use of guards for logics with data
  • Katarzyna Rybarczyk and Krzysztof Krzywdziński. Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing Protocols
  • Anne-Marie Kermarrec and Christopher Thraves. Can everybody sit closer to their friends than their enemies?
  • Edith Hemaspaandra and Henning Schnoor. A Universally Defined Undecidable Unimodal Logic
  • Laurent Doyen, Thierry Massart and Mahsa Shirmohammadi. Infinite Synchronizing Words for Probabilistic Automata
  • Paolo Baldan, Fabio Gadducci and Pawel Sobocinski. Adhesivity is not enough: Local Church-Rosser revisited
  • Petra Berenbrink, Robert Elsaesser, Tom Friedetzky, Lars Nagel and Thomas Sauerwald. Faster Coupon Collecting via Replication with  Applications in Gossiping
  • Michel Blockelet and Sylvain Schmitz. Model Checking Coverability Graphs of Vector Addition Systems
  • Richard J. Lipton, Kenneth Regan and Atri Rudra. Symmetric Functions Capture General Functions
  • Benedikt Bollig, Aiswarya Cyriac, Paul Gastin and Marc Zeitoun. Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking
  • Sebastian Bauer, Uli Fahrenberg, Line Juhl, Kim G Larsen, Axel Legay and Claus Thrane. Quantitative Refinement for Weighted Modal Transition Systems
  • Remi Bonnet. The reachability problem for Vector Addition Systems with one zero-test