Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II

Front Matter....Pages -
On r -Simple k -Path....Pages 1-12
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs....Pages 13-24
Zero Knowledge and Circuit Minimization....Pages 25-32
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity....Pages 33-44
 $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability....Pages 45-56
Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set....Pages 57-68
Network-Based Dissolution....Pages 69-80
On Unification of QBF Resolution-Based Calculi....Pages 81-93
Minimum Planar Multi-sink Cuts with Connectivity Priors....Pages 94-105
The Price of Envy-Freeness in Machine Scheduling....Pages 106-117
On the Complexity of Some Ordering Problems....Pages 118-129
The Relationship between Multiplicative Complexity and Nonlinearity....Pages 130-140
 Dual Connectedness of Edge-Bicolored Graphs and Beyond ....Pages 141-152
Combinatorial Voter Control in Elections....Pages 153-164
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas....Pages 165-176
On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields....Pages 177-188
Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth....Pages 189-200
Probabilistic Analysis of Power Assignments....Pages 201-212
Existence of Secure Equilibrium in Multi-player Games with Perfect Information....Pages 213-225
An Efficient Quantum Algorithm for Finding Hidden Parabolic Subgroups in the General Linear Group....Pages 226-238
A Note on the Minimum Distance of Quantum LDPC Codes....Pages 239-250
Minimum Bisection Is NP-hard on Unit Disk Graphs....Pages 251-262
Query-Competitive Algorithms for Cheapest Set Problems under Uncertainty....Pages 263-274
Streaming Kernelization....Pages 275-286
A Reconfigurations Analogue of Brooks’ Theorem....Pages 287-298
Intersection Graphs of L-Shapes and Segments in the Plane....Pages 299-310
Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes....Pages 311-323
Editing to a Connected Graph of Given Degrees....Pages 324-335
Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth....Pages 336-347
On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity....Pages 348-359
New Results for Non-Preemptive Speed Scaling....Pages 360-371
Lower Bounds for Splittings by Linear Combinations....Pages 372-383
On the Complexity of List Ranking in the Parallel External Memory Model....Pages 384-395
Knocking Out P k -free Graphs....Pages 396-407
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis....Pages 408-419
Affine Consistency and the Complexity of Semilinear Constraints....Pages 420-431
Small Complexity Classes for Computable Analysis....Pages 432-444
Two Results about Quantum Messages....Pages 445-456
Parameterized Approximations via d - Skew-Symmetric Multicut ....Pages 457-468
On the Clique Editing Problem....Pages 469-480
On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic....Pages 481-492
Computational Complexity of Covering Three-Vertex Multigraphs....Pages 493-504
Finding Maximum Common Biconnected Subgraphs in Series-Parallel Graphs....Pages 505-516
On Coloring Resilient Graphs....Pages 517-528
Document Retrieval with One Wildcard....Pages 529-540
An H n/2 Upper Bound on the Price of Stability of Undirected Network Design Games....Pages 541-552
Traveling Salesman Problems in Temporal Graphs....Pages 553-564
Inferring Strings from Lyndon Factorization....Pages 565-576
Betweenness Centrality – Incremental and Faster....Pages 577-588
Deterministic Parameterized Algorithms for the Graph Motif Problem....Pages 589-600
The Two Queries Assumption and Arthur-Merlin Classes....Pages 601-612
Flexible Bandwidth Assignment with Application to Optical Networks....Pages 613-624
Approximation Algorithms for Bounded Color Matchings via Convex Decompositions....Pages 625-636
Back Matter....Pages -