Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II

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