Theory and applications of models of computation

Mehr zum Buch

Inhaltsverzeichnis: Plenary Talks, New Research Directions in the Information Age, The Laplacian Paradigm: Emerging Algorithms for Massive Graphs. Special Sessions include topics such as Proof Complexity of Non-classical Logics, Optimal Acceptors and Proof Systems, and the Complexity of Geometric Problems in High Dimensions. Different Approaches to Proof Systems and Algebraic Proofs over Noncommutative Formulas are also discussed. Contributed Papers cover Nonlocal Quantum XOR Games for Many Players, Nontriviality for Exponential Time regarding Weak Reducibilities, and Streaming Algorithms in Log-Space. Additional topics include Temperature Aware Online Scheduling, Solution Concepts for Matching Games, Binary De Bruijn Partial Words, and Complexity Invariance of Real Interpretations. Other areas of focus are Pivot and Loop Complementation on Graphs, the Minimum Breakpoint Linearization Problem, and an algorithm for Minimal Interval Completion. The text also explores Centdian Computation for Sensor Networks, Twisted Jacobi Intersections Curves, and NP-Completeness in L(2,1,1)-Labeling for Trees. The complexity of Paths in Arc-Colored Digraphs, the Max k-Cut Game, and Kernel Algorithms for Dense Triplet Inconsistency are highlighted. Incremental List Coloring, Schnyder Greedy Routing, and the hardness of Clique-Width are examined. The discussion includes Deterministic Polynomial-Time Algorithms for Short DNA Words, Hamiltonian Cy