36. MFCS 2011: Warsaw, Poland

Invited Papers

• Alexandr Andoni:
  Nearest Neighbor Search in High-Dimensional Spaces. 1
  
• Jörg Flum:
  Invariantization of Listings. 2
  
• Mai Gehrke:
  Duality and Recognition. 3-18
  
• Daniel Kirsten:
  Some Variants of the Star Height Problem. 19-33
  
• Prasad Raghavendra:
  Generic Techniques to Round SDP Relaxations. 34
  
• Paul Wollan:
  New Proofs in Graph Minors. 35
  

Contributed Papers

• Yoram Bachrach:
  The Least-Core of Threshold Network Flow Games. 36-47
  
• Paolo Baldan, Fabio Gadducci, Pawel Sobocinski:
  Adhesivity Is Not Enough: Local Church-Rosser Revisited. 48-59
  
• Sebastian S. Bauer, Uli Fahrenberg, Line Juhl, Kim G. Larsen, Axel Legay, Claus R. Thrane:
  Quantitative Refinement for Weighted Modal Transition Systems. 60-71
  
• Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Lars Nagel, Thomas Sauerwald:
  Faster Coupon Collecting via Replication with Applications in Gossiping. 72-83
  
• Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer:
  Verifying Proofs in Constant Depth. 84-95
  
• Markus Bläser, Radu Curticapean:
  The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree. 96-107
  
• Michel Blockelet, Sylvain Schmitz:
  Model Checking Coverability Graphs of Vector Addition Systems. 108-119
  
• Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka:
  Hard Functions for Low-Degree Polynomials over Prime Fields. 120-131
  
• Benedikt Bollig, Aiswarya Cyriac, Paul Gastin, Marc Zeitoun:
  Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking. 132-144
  
• Rémi Bonnet:
  The Reachability Problem for Vector Addition System with One Zero-Test. 145-157
  
• Christina Boucher:
  The Bounded Search Tree Algorithm for the Closest String Problem Has Quadratic Smoothed Complexity. 158-169
  
• Olivier Bournez, Daniel S. Graça, Amaury Pouly:
  Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains. 170-181
  
• Robert Bredereck, André Nichterlein, Rolf Niedermeier, Geevarghese Philip:
  Pattern-Guided Data Anonymization and Clustering. 182-193
  
• Stanislav Böhm, Stefan Göller:
  Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-Complete. 194-205
  
• Krishnendu Chatterjee, Laurent Doyen:
  Energy and Mean-Payoff Parity Markov Decision Processes. 206-218
  
• Jacek Chrzaszcz, Aleksy Schubert:
  The Role of Polymorphism in the Characterisation of Complexity by Soft Types. 219-230
  
• David A. Cohen, Páidí Creed, Peter G. Jeavons, Stanislav Zivny:
  An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection. 231-242
  
• Thomas Colcombet, Clemens Ley, Gabriele Puppis:
  On the Use of Guards for Logics with Data. 243-255
  
• Evgeny Demenkov, Alexander S. Kulikov:
  An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers. 256-265
  
• Riccardo Dondi, Giancarlo Mauri, Italo Zoppis:
  On the Complexity of the l-diversity Problem. 266-277
  
• Laurent Doyen, Thierry Massart, Mahsa Shirmohammadi:
  Infinite Synchronizing Words for Probabilistic Automata. 278-289
  
• Balder ten Cate, Alessandro Facchini:
  Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs. 290-302
  
• John Fearnley, Oded Lachish:
  Parity Games on Graphs with Medium Tree-Width. 303-314
  
• Peter Franek, Stefan Ratschan, Piotr Zgliczynski:
  Satisfiability of Systems of Equations of Real Analytic Functions Is Quasi-decidable. 315-326
  
• Pawel Gawrychowski, Artur Jez, Andreas Maletti:
  On Minimising Automata with Errors. 327-338
  
• Petr A. Golovach, Marcin Kaminski, Daniël Paulusma:
  Contracting a Chordal Graph to a Split Graph or a Tree. 339-350
  
• Marats Golovkins, Maksim Kravtsev, Vasilijs Kravcevs:
  Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages. 351-363
  
• Edith Hemaspaandra, Henning Schnoor:
  A Universally Defined Undecidable Unimodal Logic. 364-375
  
• Jun Hosoda, Juraj Hromkovic, Taisuke Izumi, Hirotaka Ono, Monika Steinová, Koichi Wada:
  On the Approximability of Minimum Topic Connected Overlay and Its Special Instances. 376-387
  
• Anne-Marie Kermarrec, Christopher Thraves:
  Can Everybody Sit Closer to Their Friends Than Their Enemies? 388-399
  
• Vladimir Kolmogorov:
  Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions. 400-411
  
• Andreas Krebs, Nutan Limaye, Srikanth Srinivasan:
  Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions. 412-423
  
• Dietrich Kuske, Thomas Weidner:
  Size and Computation of Injective Tree Automatic Presentations. 424-435
  
• Richard J. Lipton, Kenneth W. Regan, Atri Rudra:
  Symmetric Functions Capture General Functions. 436-447
  
• Markus Lohrey:
  Compressed Word Problems for Inverse Monoids. 448-459
  
• Andreas Maletti, Daniel Quernheim:
  Pushing for Weighted Tree Automata. 460-471
  
• Florin Manea, Robert Mercas, Catalin Tiseanu:
  Periodicity Algorithms for Partial Words. 472-484
  
• Alexander Okhotin, Kai Salomaa:
  State Complexity of Operations on Input-Driven Pushdown Automata. 485-496
  
• Christophe Paul, Anthony Perez, Stéphan Thomassé:
  Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem. 497-507
  
• Kevin Perrot, Eric Rémila:
  Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence. 508-519
  
• Michal Pilipczuk:
  Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach. 520-531
  
• Wladimir Fridman, Bernd Puchala:
  Distributed Synthesis for Regular and Contextfree Specifications. 532-543
  
• Krzysztof Krzywdzinski, Katarzyna Rybarczyk:
  Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing Protocols. 544-555
  
• Ocan Sankur:
  Untimed Language Preservation in Timed Systems. 556-567
  
• Kei Uchizawa, Eiji Takimoto:
  Lower Bounds for Linear Decision Trees via an Energy Complexity Argument. 568-579
  
• Michael Vanden Boom:
  Weak Cost Monadic Logic over Infinite Trees. 580-591
  
• Jianxin Wang, Yongjie Yang, Jiong Guo, Jianer Chen:
  Linear Problem Kernels for Planar Graph Problems with Small Distance Property. 592-603
  
• Mingyu Xiao, Ton Kloks, Sheung-Hung Poon:
  New Parameterized Algorithms for the Edge Dominating Set Problem. 604-615
  

Last update Fri May 25 08:26:28 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page