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

Monday, August 22
9:00 Conference opening
9:10 Invited lecture: Mai Gehrke Duality and recognition
10:30 Coffee break
11:00 Complexity and lower bounds Synthesis and verification
E. Demenkov, A. Kulikov An Elementary Proof of a 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
O. Beyersdorff, S. Datta, M. Mahajan, G. Scharfenberger-Fabian, K. Sreenivasaiah, M. Thomas, H. Vollmer Verifying Proofs in Constant Depth
K. Uchizawa, E. Takimoto Lower Bounds for Linear Decision Trees via An Energy Complexity Argument
B. Puchala, W. Fridman Distributed Synthesis for Regular and Contextfree Specifications
B. Bollig, A. Cyriac, P. Gastin, M. Zeitoun Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking
S. Bauer, U. Fahrenberg, L. Juhl, K. G. Larsen, A. Legay, C. Thrane Quantitative Refinement for Weighted Modal Transition Systems
12:30 Lunch
14:00 Invited lecture: Paul Wollan New Proofs in Graph Minors
15:30 Coffee break
16:00 Young Researchers Forum: Graphs and Algorithms
K. Junosza-Szaniawski, J. Kratochvil, M. Liedloff, P. Rossmanith, P. Rzążewski Fast Exact Algorithm for L(2,1)-Labeling of Graphs
J. Arjona, A. Fernández Anta Exact Bisection Width of the Torus and Other Multidimensional Product Graphs
A. Nenca, J. Dybizbański Oriented chromatic number of grids
16:45 Coffee break
17:00 Young Researchers Forum: Algorithms I
O. Moriš Generalized Maneuvers in Route Planning SEQ
N. Nicolaou Seeking Fast Operations in MWMR Atomic Register Implementations
S. Köhler Fault-containing Self-stabilization
M. Pilipczuk The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)
18:00 Welcome reception at Kazimierzowski Palace
Tuesday, August 23
9:00 Invited lecture: Daniel Kirsten Some Variants of the Star Height Problem
10:30 Coffee break
11:00 Parametrized complexity Logic
C. Paul, S. Thomassé, A. Perez Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and related problems
J. Wang, Y. Yang, J. Guo, J. Chen Linear Problem Kernels for Planar Graph Problems with Small Distance Property
M. Xiao, T. Kloks, S. Poon New Parameterized Algorithms for Edge Dominating Set
E. Hemaspaandra, H. Schnoor A Universally Defined Undecidable Unimodal Logic
A. Facchini, B. Ten Cate Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs
M. Vanden Boom Weak Cost Monadic Logic Over Infinite Trees
12:30 Lunch
14:00 Math and physics Logic, automata, words
P. Franek, S. Ratschan, P. Zgliczynski Satisfiability of Systems of Equations of Real Analytic Functions is Quasi-decidable
O. Bournez, D. Graça, A. Pouly Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains
K. Perrot, E. Rémila Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence
D. Kuske, T. Weidner Size and computation of injective tree automatic presentations
M. Lohrey Compressed word problems for inverse monoids
M. Pilipczuk Problems parameterized by treewidth tractable in single exponential time: a logical approach
15:30 Coffee break
16:00 Young Researchers Forum: Automata and Languages I
F. Mazowiecki Continuous reductions of regular languages
D. Quernheim Hyper-minimisation of weighted finite automata Aspects of non-deterministic finite automata minimisation
M. Bilkowski Strongly unambiguous regular languages of infinite trees
16:45 Coffee break
17:00 Young Researchers Forum: Logic and Games
M. Skrzypczak Equational theories of profinite structures
W. Charatonik, P. Witkowski Complexity of Two-Variable Logics Extended with Monadic Datalog Programs
O. Skibski Steady Marginality: A Uniform Approach to Shapley Value for Games with Externalities
J. Ortega The Effects of Tie-Breaking Rules on Repeated Auctions with Discrete Bidding
Wednesday, August 24
9:00 Invited lecture: Prasad Raghavendra Generic techniques to round SDP relaxations
10:30 Coffee break
11:00 String algorithms Quantitative and quantum automata
C. Boucher The Bounded Search Tree Algorithm for the Closest String Problem has Quadratic Smoothed Complexity
F. Manea, R. Mercas, C. Tiseanu Periodicity Algorithms for Partial Words
A. Krebs, N. Limaye, S. Srinivasan Streaming algorithms for recognizing nearly well-parenthesized expressions
A. Maletti and D. Quernheim Pushing for weighted tree automata
O. Sankur Untimed Language Preservation in Timed Systems
M. Golovkins, M. Kravtsev, V. Kravcevs Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
12:30 Lunch
13:30 Young Researchers Forum: Algorithms II
P. Floderus Preventing Cactus Fire SEQ
P. Gawrychowski Optimal (fully) LZW-compressed pattern matching
14:00 Coffee break
14:15 Young Researchers Forum: Automata and Languages II
G. Madejski Permutation languages D. Quernheim Hyper-minimisation of weighted finite automata
K. Moroz A dynamic parsing algorithm for pregroup grammars
15:00 Social event
Thursday, August 25
9:00 Invited lecture: Jörg Flum Invariantization of listings
10:30 Coffee break
11:00 Graphs Automata
A.-M. Kermarrec, C. Thraves Can everybody sit closer to their friends than their enemies?
P. Golovach, M. Kaminski, D. Paulusma Contracting a chordal graph to a split graph or a tree
M. Blaeser, R. Curticapean The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree
P. Gawrychowski, A. Jeż, A. Maletti On minimising automata with errors
A. Okhotin, K. Salomaa State complexity of operations on input-driven pushdown automata
S. Böhm, S. Göller Language equivalence of deterministic real-time one-counter automata is NL-complete
12:30 Lunch
14:00 Invited lecture: Alexandr Andoni Nearest Neighbor Search in High-Dimensional Spaces
15:30 Coffee break
16:00 Social networks and k-anonymity VAS and data words
R. Bredereck, A. Nichterlein, R. Niedermeier, G. Philip Pattern-Guided Data Anonymization and Clustering
R. Dondi, G. Mauri, I. Zoppis On the Complexity of the l-diversity Problem
J. Hosoda, J. Hromkovic, T. Izumi, H. Ono, M. Steinová, K. Wada On the Approximability of Minimum Topic Connected Overlay and Its Special Instances
R. Bonnet The reachability problem for Vector Addition Systems with one zero-test
M. Blockelet, S. Schmitz Model Checking Coverability Graphs of Vector Addition Systems
T. Colcombet, C. Ley, G. Puppis On the use of guards for logics with data
17:30 Break
19:00 Conference dinner
Friday, August 26
9:00 Functions Games and automata
A. Bogdanov, A. Kawachi, H. Tanaka Hard Functions for Low-degree Polynomials over Prime Fields
R. J. Lipton, K. Regan, A. Rudra Symmetric Functions Capture General Functions
V. Kolmogorov Submodularity on a tree: Unifying L-convex and bisubmodular functions
J. Fearnley, O. Lachish Parity Games On Graphs With Medium Tree-width
K. Chatterjee, L. Doyen Energy and Mean-Payoff Parity Markov Decision Processes
L. Doyen, T. Massart, M. Shirmohammadi Infinite Synchronizing Words for Probabilistic Automata
10:30 Coffee break
11:00 Networks and distributed algorithms Algebra and types
K. Rybarczyk, K. Krzywdziński Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing Protocols
P. Berenbrink, R. Elsaesser, T. Friedetzky, L. Nagel, T. Sauerwald Faster Coupon Collecting via Replication with Applications in Gossiping
Y. Bachrach The Least-Core of Threshold Network Flow Games
D. A. Cohen, P. Creed, P. G. Jeavons, S. Zivny An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
J. Chrząszcz, A. Schubert The role of polymorphism in the characterisation of complexity by soft types
P. Baldan, F. Gadducci, P. Sobocinski Adhesivity is not enough: Local Church-Rosser revisited
12:30 Lunch