
Theory and Applications of Models of Computation
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Talk 1
- Designing Algorithms with Limited Work Space
- Session 1A: General Algorithms
- Group-Theoretic Lower Bounds for the Complexity of Matrix Multiplication
- Introduction
- Lower Bounds for the Complexity of Matrix Multiplication
- Lower Bounds for the Bilinear Complexity of Group Algebras
- Conclusion
- References
- A Real Elementary Approach to the Master Recurrence and Generalizations
- Introduction
- On Master Theorems
- Two Generalized Master Theorems
- Elementary Summation Techniques
- Elementary Sums and Proof of Theorem A
- Real Induction and Proof of Theorem B
- Conclusion
- References
- Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines
- Introduction
- Preliminaries
- Classified Round Robin (CRR)
- Dual-Classified Round Robin (DCRR)
- The Algorithm
- Framework of the Analysis and Nice Job Sets
- Analysis of DCRR
- Conclusion
- References
- Session 1B: Approximation I
- Approximating Edge Dominating Set in Dense Graphs
- Introduction
- Problem Statement
- Related Work
- Our Contributions
- Subset Edge Dominating Set Problem
- Definitions and Notations
- Algorithm ASEDS
- Analysis of ASEDS
- Dense Instances of the MEDS Problem
- Approximation Hardness Results
- References
- Near Approximation of MaximumWeight Matching through Efficient Weight Reduction
- Introduction
- Our Contributions
- Other Related Results
- Simple Edge Weight Transformations
- A Transformation into an (-)-Approximation Algorithm
- Applications
- Extensions
- Final Remark
- References
- Approximability of the Subset Sum Reconfiguration Problem
- Introduction
- Complexity and Inapproximability
- PTAS
- Large Items
- Small Items
- General Instance
- Analysis of the Algorithm
- Concluding Remark
- References
- Session 2A: Graph Algorithms I
- An Improved Kernel for Planar Connected Dominating Set
- Introduction
- Preliminaries
- Data Reduction Rules
- Improved Kernel for Planar Connected Dominating Set
- References
- Fast Exact Algorithm for L(2, 1)-Labeling of Graphs
- Introduction
- Auxiliary Combinatorial Results
- Exact Algorithm for L(2,1)-Labeling
- Pseudocode of the Algorithm
- References
- An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
- Introduction
- Improved Sufficient Condition and Its Tightness
- Proof of Theorem 2
- Overview and Definitions
- Algorithm
- Conclusion
- References
- Session 2B: Complexity I
- A Compact Encoding of Unordered Binary Trees
- Introduction
- Pair-Single Decomposition
- Encoding
- Decoding
- Conclusion
- References
- Low Distortion Metric Embedding into Constant Dimension
- Introduction
- Previous Results
- Preliminaries
- Results
- Conclusion
- References
- A Better Upper Bound on Weights of Exact Threshold Functions
- Introduction
- Preliminary
- Constant Dimension Case
- General Construction
- Conclusion
- References
- Session 3A: Optimization I
- Submodular Function Minimization under a Submodular Set Covering Constraint
- Introduction
- Preliminaries
- Submodular Functions
- Integer Programming Formulation
- Algorithm
- Analysis
- Application
- The Submodular Cost Set Cover Problem
- References
- Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions
- Introduction
- Characterizations of Quadratic Utility Functions
- Results for Submodular Utility Functions
- Results for Supermodular Utility Functions
- References
- Session 3B: Circuit Complexity
- Energy and Fan-In of Threshold Circuits Computing Mod Functions
- Introduction
- Preliminaries
- Our Results
- Upper Bound
- Lower Bound
- Proof of Lemma 1
- Conclusions
- References
- NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(log log n) Depth
- Introduction
- Related Work
- Preliminaries
- Main Result
- A Fast Satisfiability Algorithm
- Proof of Main Theorem
- Discussions
- References
- Invited Talk 2
- Quantum Complexity: Some Recent Results, Some Open Problems, Some Thoughts
- Session 4A: Data Structures
- Non-adaptive Complex Group Testing with Multiple Positive Sets
- Introduction
- Preliminaries
- Existence of ("7016d,"7016s)-Separable Matrix
- Constructing a ("7016d,"7016s)-Separable Matrix
- The Derandomized Algorithm
- Computing the Probability
- Conclusions
- References
- How to Cut a Graph into Many Pieces
- Introduction
- Complexity Results
- An FPT Algorithm and an EPTAS for Planar Graphs
- Conclusion
- References
- Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet
- Introduction
- Preliminaries
- Data Structure and Static Operations
- Tree Topology of Micro Trees
- Edge Labels of Micro Trees
- Frontiers of Micro Trees
- Pointers to Other Micro Trees
- Subtree Sizes
- Update Operations
- References
- Integer Representations towards Efficient Counting in the Bit Probe Model
- Introduction
- Space-Optimal Counters with Increment and Decrement
- Constructing (n,n-1,3)-Counter Using (4,3,2)-Counter
- Redundant Counters with Increment
- Counters with One Bit Redundancy
- One Bit Read-Write Trade-Off
- Forbidden State Counter with Increment
- Counters with Increment and Decrement
- Addition and Subtraction
- Conclusion
- References
- Session 4B: Logic and Formal Language Theory
- Closed Left-R.E. Sets
- Introduction
- Many-One Closed Left-R.E. Sets
- Ascending Closed Left-R.E. Sets
- References
- $?^0_1$ Sets and Tilings
- Preliminaries
- $?^0_1$ Sets and Degrees
- Tilings and SFTs
- $?^0_1$ Sets and Origin Constrained Tilings
- The Tileset
- $?^0_1$ Sets and Tilings
- References
- Intuitive Probability Logic
- Introduction
- Semantics and Syntax
- A Guided Maximally Consistent Extension Theorem
- Three-Dimensional Language
- Guided Maximally Consistent Extension
- Two Applications
- Satisfiability of a Probability Formula and Solvability of Its Corresponding System of Linear Inequalities
- Canonical Finitely-Additive Probability Models Are Not a Probability Model
- References
- An Algebraic Characterization of Strictly Piecewise Languages
- Introduction
- Preliminaries
- Piecewise Testable and Strictly Piecewise Languages
- Algebraic Characterization of SP
- Algorithms for SP Languages
- Deciding SP
- Finding the Shortest Forbidden Subsequences
- Conclusion
- References
- Session 5A: Graph Algorithms II
- Deterministic Algorithms for Multi-criteria TSP
- Multi-criteria TSP
- Previous Work
- New Results
- Max-ATSP
- Max-STSP
- Cycle Cover Algorithm for Min-TSP
- Open Problems
- References
- Extending Partial Representations of Interval Graphs
- Introduction
- Extending Interval Graphs
- Extending Proper Interval Graphs
- Simultaneous Interval Graphs
- Conclusions
- Constructing All Representations
- Allen Algebras
- Extending Unit Interval Representations
- References
- Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way
- Introduction
- Notation and Basic Concepts
- Split Composition and Decomposition
- Extending Distance-Hereditary Graphs
- Algorithmic Problems
- Recognition Problem
- Computing the Stretch Number
- Other Problems
- Relationships between Gen(
- P3,C3,C5 ) and DH(k)
- References
- Session 5B: Approximation II
- The Complexity and Approximability of Minimum Contamination Problems
- Introduction
- The Complexity of the Minimum Contamination Problems
- Approximation Algorithms for the Minimum Contamination Problems
- Bicriteria Approximation Algorithms for the Minimum Contamination Problems
- Approximation Hardness of the Minimum Contamination Problems
- Conclusion
- References
- On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric
- Introduction and Related Work
- Preliminaries
- The Complexity in Low Dimensions
- The Steiner Ratio
- Applications
- Conclusion
- References
- Lower Bounds for Testing Computability by Small Width OBDDs
- Introduction
- Results for Width-2 and Width-3 OBDDs
- Results for Width-w OBDDs, for Constant w 4
- Techniques
- Preliminaries
- Reducing Communication Problems to Testing Problems
- Communication Complexity Problems
- Branching Program Basics
- A Lower Bound for Testing Fixed-Order Width-2 and Width-3 OBDDs
- A Lower Bound for Testing Arbitrary-Order Width-2 OBDDs
- A Lower Bound for Testing Fixed-Order Width-w OBDDs, for Constant w 4.
- References
- Session 6A: Games and Learning Theory
- On the Amount of Nonconstructivity in Learning Recursive Functions
- Introduction
- Preliminaries
- Results
- Conclusions and Open Problems
- References
- A Bad Instance for k-Means++
- Introduction
- Construction and Analysis of a Bad Instance
- Construction
- Reduction to a Markov Chain
- How to Choose ?
- Analysis of the Markov Chain
- Conclusion
- References
- Catching a Fast Robber on Interval Graphs
- Introduction
- Preliminaries
- Specifics of the Game
- Essential Cops' Moves
- Simulating General Cops' Strategy
- Complexity of Finding Witness
- Conclusion
- References
- Some Tractable Win-Lose Games
- Introduction
- Outline of Proof
- Background and Preliminaries
- Win-Lose Bimatrix Games
- Minor-Free Graphs
- Triconnected Decomposition of a Graph
- Finding a Nash Equilibrium
- Stitching Cycles Together
- Undominated Induced Cycle in K5
- Undominated Induced Cycle in V8
- Conclusion and Future Work
- References
- Session 6B: Cryptography and Communication Complexity
- A Note on Obfuscation for Cryptographic Functionalities of Secret-Operation Then Public-Encryption
- Introduction
- Preliminaries
- Our Result
- Obfuscation for the General Functionality
- Application to Encrypted Signature
- Application to Sign-Then-Encrypt
- Application to Re-encryption
- References
- Grey-Box Steganography
- Introduction
- Basic Notation and Definitions
- A Grey-Box Model for Steganography
- The Monomial Covertext Channels
- Stegosystem for Monomial Channels
- Conclusions and Future Work
- References
- Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models
- Introduction
- Preliminaries
- A Public-Coin Protocol in the SMP Model
- References
- The Hardness of Median in the Synchronized Bit Communication Model
- Introduction
- Preliminaries
- Round Complexity of Strategy
- Reduction from Strategy to Median
- Conclusions
- References
- Session 7A: Optimization II
- Lower Bounds for the Smoothed Number of Pareto Optimal Solutions
- Introduction
- The Bi-criteria Case
- The Multi-criteria Case
- References
- Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands
- Introduction
- O(d*logd*)-Approximation Algorithm for -SLP
- Formulation of the Source Location Problem with Vertex-Connectivity
- (2d*-1)-Approximation Algorithm to RVSAP
- Conclusion
- References
- Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects
- Introduction
- Preliminaries
- Approximability
- Algorithm SPA-P-APPROX-PROMOTION
- Correctness
- Analysis of the Approximation Ratio
- Tightness of the Analysis
- Inapproximability
- Conclusions
- References
- Session 7B: Complexity II
- Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
- Introduction
- Preliminaries
- Graphs
- Spanning Tree Congestion ofWeighted Graphs
- Graph Classes
- Hardness for Split Graphs and Chain Graphs
- Hardness for Split Graphs
- Hardness for Chain Graphs
- Exponential-Time Exact Algorithm
- Remarks on Cographs
- References
- Switching to Hedgehog-Free Graphs Is NP-Complete
- Introduction
- Preliminaries
- Switching to Hedgehog-Free Graphs
- Concluding Remarks
- References
- Locally Injective Homomorphism to the Simple Weight Graphs
- Introduction
- Preliminaries
- Proof of Theorem 3 (Polynomial Case)
- Proof of Theorem 4 (NP-Complete Case)
- References
- Session 8A: Graph Algorithms III
- Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
- Introduction
- Clique Width
- Framework of Our Algorithms
- Counting Maximal Matchings
- Counting Paths and Path Matchings
- Conclusion
- References
- Hide-and-Seek: Algorithms for PolygonWalk Problems
- Introduction
- Preliminaries
- Cells and Skeletons
- The Boundary of a Cell
- Properties of the Skeleton Invisibility Diagram
- Computing a Safe Path for Jack and Jill
- Determining Skeletons for s and t
- Determining Connected Components of Skeletons
- Hide-and-Seek with Multiple Children
- Conclusion
- References
- Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
- Introduction
- Preliminaries
- The qMSO-Relation and Its Characterization
- Model Checking Games and Characteristic Trees
- Constructing Characteristic Trees
- Discussion and Conclusion
- References
- Session 8B: Complexity III
- On the Polynomial Depth of Various Sets of Random Strings
- Introduction
- Preliminaries
- Polynomial Depth
- Basic Properties of Monotone-Poly-Depth
- Slow Growth Law
- A Poly Deep Sequence
- The Set of Levin Random Strings Is Deep
- The Set of Kolmogorov-Random Strings Is Deep
- References
- Edge Contractions in Subclasses of Chordal Graphs
- Introduction
- Preliminaries
- Contractions and Induced Subgraph Isomorphisms of Trivially Perfect Graphs
- Contracting Split Graphs
- Concluding Remarks
- References
- Planarity Testing Revisited
- Introduction
- Related Work
- Comparison with AM04
- Definitions and Preliminaries
- Outline of Algorithms
- Outline of Planar Embedding Algorithm
- Outline of Algorithm to Find Kuratowski Minors
- Planarity Testing
- Reduction to the Triconnected case
- The Conflict Graph
- Inside and Outside a Fundamental Cycle
- Obtaining a Planar Embedding
- Finding Kuratowski Subgraphs
- References
- Generalized Satisfiability for the Description Logic $ALC$
- Introduction
- Preliminaries
- Complexity Results for TSAT, TCSAT, OSAT, OCSAT
- Both Quantifiers
- Restricted Quantifiers
- Conclusion
- References
- Author Index
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.