Skip to main content
SpringerLink
Log in
Book cover

Mathematical Foundations of Computer Science 2015

40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II

  • Conference proceedings
  • © 2015

Overview

Editors:
  1. Giuseppe F. Italiano

    1. University of Rome "Tor Vergata", Rome, Italy

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Giovanni Pighizzini

    1. Università degli Studi di Milano, Milan, Italy

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Donald T. Sannella

    1. University of Edinburgh, Edinburgh, United Kingdom

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 9235)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: MFCS 2015.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (50 papers)

  1. Front Matter

    Pages I-XVII
    Download chapter PDF

  2. Near-Optimal Asymmetric Binary Matrix Partitions

    • Fidaa Abed, Ioannis Caragiannis, Alexandros A. Voudouris
    Pages 1-13

  3. Dual VP Classes

    • Eric Allender, Anna Gál, Ian Mertz
    Pages 14-25

  4. On Tinhofer’s Linear Programming Approach to Isomorphism Testing

    • V. Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky
    Pages 26-37

  5. On the Complexity of Noncommutative Polynomial Factorization

    • V. Arvind, Gaurav Rattan, Pushkar Joglekar
    Pages 38-49

  6. An Algebraic Proof of the Real Number PCP Theorem

    • Martijn Baartse, Klaus Meer
    Pages 50-61

  7. On the Complexity of Hub Labeling (Extended Abstract)

    • Maxim Babenko, Andrew V. Goldberg, Haim Kaplan, Ruslan Savchenko, Mathias Weller
    Pages 62-74

  8. On the Complexity of Speed Scaling

    • Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs, Michele Scquizzato
    Pages 75-89

  9. Almost All Functions Require Exponential Energy

    • Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato
    Pages 90-101

  10. On Dynamic DFS Tree in Directed Graphs

    • Surender Baswana, Keerti Choudhary
    Pages 102-114

  11. Metric Dimension of Bounded Width Graphs

    • Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan
    Pages 115-126

  12. Equality, Revisited

    • Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck
    Pages 127-138

  13. Bounding the Clique-Width of H-free Chordal Graphs

    • Andreas Brandstädt, Konrad K. Dabrowski, Shenwei Huang, Daniël Paulusma
    Pages 139-150

  14. New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory

    • Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, Lin F. Yang
    Pages 151-162

  15. QMA with Subset State Witnesses

    • Alex Bredariol Grilo, Iordanis Kerenidis, Jamie Sikora
    Pages 163-174

  16. Phase Transition for Local Search on Planted SAT

    • Andrei A. Bulatov, Evgeny S. Skvortsov
    Pages 175-186

  17. Optimal Bounds for Estimating Entropy with PMF Queries

    • Cafer Caferov, Barış Kaya, Ryan O’Donnell, A. C. Cem Say
    Pages 187-198

  18. Mutual Dimension and Random Sequences

    • Adam Case, Jack H. Lutz
    Pages 199-210

  19. Optimal Algorithms and a PTAS for Cost-Aware Scheduling

    • Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie, José Verschae
    Pages 211-222

  20. Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

    • Ruiwen Chen
    Pages 223-234
Back to top

Other volumes

  1. Mathematical Foundations of Computer Science 2015

  2. Mathematical Foundations of Computer Science 2015

Keywords

About this book

This two volume set LNCS 9234 and 9235 constitutes the refereed conference proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015, held in Milan, Italy, in August 2015. The 82 revised full papers presented together with 5 invited talks were carefully selected from 201 submissions. The papers feature high-quality research in all branches of theoretical computer science. They have been organized in the following topical main sections: logic, semantics, automata, and theory of programming (volume 1) and algorithms, complexity, and games (volume 2).

Editors and Affiliations

  • University of Rome "Tor Vergata", Rome, Italy

    Giuseppe F. Italiano

  • Università degli Studi di Milano, Milan, Italy

    Giovanni Pighizzini

  • University of Edinburgh, Edinburgh, United Kingdom

    Donald T. Sannella

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation