Mathematical Foundations of Computer Science 2011

1. Front Matter

   PDF

2. Invited Papers

   1. Nearest Neighbor Search in High-Dimensional Spaces

      • Alexandr Andoni

      Pages 1-1

   2. Invariantization of Listings

      • Jörg Flum

      Pages 2-2

   3. Duality and Recognition

      • Mai Gehrke

      Pages 3-18

   4. Some Variants of the Star Height Problem

      • Daniel Kirsten

      Pages 19-33

   5. Generic Techniques to Round SDP Relaxations

      • Prasad Raghavendra

      Pages 34-34

   6. New Proofs in Graph Minors

      • Paul Wollan

      Pages 35-35

3. Contributed Papers

   1. The Least-Core of Threshold Network Flow Games

      • Yoram Bachrach

      Pages 36-47

   2. Adhesivity Is Not Enough: Local Church-Rosser Revisited

      • Paolo Baldan, Fabio Gadducci, Pawel Sobociński

      Pages 48-59

   3. Quantitative Refinement for Weighted Modal Transition Systems

      • Sebastian S. Bauer, Uli Fahrenberg, Line Juhl, Kim G. Larsen, Axel Legay, Claus Thrane

      Pages 60-71

   4. Faster Coupon Collecting via Replication with Applications in Gossiping

      • Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Lars Nagel, Thomas Sauerwald

      Pages 72-83

   5. Verifying Proofs in Constant Depth

      • Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas et al.

      Pages 84-95

   6. The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree

      • Markus Bläser, Radu Curticapean

      Pages 96-107

   7. Model Checking Coverability Graphs of Vector Addition Systems

      • Michel Blockelet, Sylvain Schmitz

      Pages 108-119

   8. Hard Functions for Low-Degree Polynomials over Prime Fields

      • Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka

      Pages 120-131

   9. Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking

      • Benedikt Bollig, Aiswarya Cyriac, Paul Gastin, Marc Zeitoun

      Pages 132-144

   10. The Reachability Problem for Vector Addition System with One Zero-Test

       • Rémi Bonnet

       Pages 145-157

   11. The Bounded Search Tree Algorithm for the Closest String Problem Has Quadratic Smoothed Complexity

       • Christina Boucher

       Pages 158-169

   12. Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains

       • Olivier Bournez, Daniel S. Graça, Amaury Pouly

       Pages 170-181

   13. Pattern-Guided Data Anonymization and Clustering

       • Robert Bredereck, André Nichterlein, Rolf Niedermeier, Geevarghese Philip

       Pages 182-193

This volume constitutes the refereed proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011, held in Warsaw, Poland, in August 2011. The 48 revised full papers presented together with 6 invited talks were carefully reviewed and selected from 129 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, grammars and formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, cryptography and security, databases and knowledge-based systems, formal specifications and program development, foundations of computing, logic in computer science, mobile computing, models of computation, networks, parallel and distributed computing, quantum computing, semantics and verification of programs, and theoretical issues in artificial intelligence.

• constraint optimization
• finite automata
• graph drawing
• modal logic
• weighted polymorphisms
• algorithm analysis and problem complexity
• data structures

• Institute of Informatics, University of Warsaw, Warsaw, Poland

  Filip Murlak, Piotr Sankowski

Policies and ethics