Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II (Lecture Notes in Computer Science Book 9235)

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). Front Matter....Pages I-XVII Near-Optimal Asymmetric Binary Matrix Partitions....Pages 1-13 Dual VP Classes....Pages 14-25 On Tinhofer’s Linear Programming Approach to Isomorphism Testing....Pages 26-37 On the Complexity of Noncommutative Polynomial Factorization....Pages 38-49 An Algebraic Proof of the Real Number PCP Theorem....Pages 50-61 On the Complexity of Hub Labeling (Extended Abstract)....Pages 62-74 On the Complexity of Speed Scaling....Pages 75-89 Almost All Functions Require Exponential Energy....Pages 90-101 On Dynamic DFS Tree in Directed Graphs....Pages 102-114 Metric Dimension of Bounded Width Graphs....Pages 115-126 Equality, Revisited....Pages 127-138 Bounding the Clique-Width of H-free Chordal Graphs....Pages 139-150 New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory....Pages 151-162 QMA with Subset State Witnesses....Pages 163-174 Phase Transition for Local Search on Planted SAT....Pages 175-186 Optimal Bounds for Estimating Entropy with PMF Queries....Pages 187-198 Mutual Dimension and Random Sequences....Pages 199-210 Optimal Algorithms and a PTAS for Cost-Aware Scheduling....Pages 211-222 Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases....Pages 223-234 Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem....Pages 235-247 Network Creation Games: Think Global – Act Local....Pages 248-260 Oblivious Transfer from Weakly Random Self-Reducible Public-Key Cryptosystem....Pages 261-273 Efficient Computations over Encrypted Data Blocks ....Pages 274-286 Polynomial Kernels for Weighted Problems....Pages 287-298 A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time....Pages 299-310 Metastability of Asymptotically Well-Behaved Potential Games....Pages 311-323 The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials....Pages 324-335 Parameterized Algorithms for Parity Games....Pages 336-347 Algorithmic Applications of Tree-Cut Width....Pages 348-360 Log-Concavity and Lower Bounds for Arithmetic Circuits....Pages 361-371 Easy Multiple-Precision Divisors and Word-RAM Constants....Pages 372-383 The Price of Connectivity for Cycle Transversals....Pages 384-394 Upper and Lower Bounds on Long Dual Paths in Line Arrangements....Pages 395-406 A Numbers-on-Foreheads Game....Pages 407-419 Faster Lightweight Lempel-Ziv Parsing....Pages 420-431 Parallel Identity Testing for Skew Circuits with Big Powers and Applications....Pages 432-444 On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape....Pages 445-458 Densest Subgraph in Dynamic Graph Streams....Pages 459-471 The Offline Carpool Problem Revisited....Pages 472-482 On Sampling Simple Paths in Planar Graphs According to Their Lengths....Pages 483-492 Degree-Constrained Subgraph Reconfiguration is in P....Pages 493-504 Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel....Pages 505-516 Efficient Equilibria in Polymatrix Coordination Games....Pages 517-528 Finding Consensus Strings with Small Length Difference Between Input and Solution Strings....Pages 529-541 Active Linking Attacks....Pages 542-554 On the Complexity of Master Problems....Pages 555-566 Efficient Algorithm for Computing All Low s-t Edge Connectivities in Directed Graphs....Pages 567-576 Maximum Minimal Vertex Cover Parameterized by Vertex Cover....Pages 577-588 Fast Dynamic Weight Matchings in Convex Bipartite Graphs....Pages 589-600 Back Matter....Pages 601-612 ....Pages 613-615