Theory and Applications of Models of Computation

Name: Theory and Applications of Models of Computation | 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011, Proceedings

Mitsunori Ogihara Jun Tarui(Herausgeber*in)

Springer (Verlag)

Erschienen am 27. April 2011

XVI, 564 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-20877-5 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken