Theory and Applications of Models of Computation

Name: Theory and Applications of Models of Computation | 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings

Manindra Agrawal Barry S. Cooper Angsheng Li(Herausgeber*in)

Springer (Verlag)

Erschienen am 4. Mai 2012

XV, 622 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-29952-0 (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
Turing Lectures 2012
On the Impact of Turing Machines
From Turing Machine to Morphogenesis: Forming and Informing Computation
From Describing Information, to the Mathematics of Causality
Universality, Turing Completeness and Programs as Information
Journeys beyond the Computable
Modelling the Brain
The Return to Embodied Computation
References
Theory of Computation as an Enabling Tool for the Sciences
Interaction and Collective Intelligence on the Internet
Uncertainty on the Internet
The Limitations of Turing Model and Interaction Machine Model beyond Turing Machines
Topological Potential
Collective Intelligence on the Internet
References
What Computers Do: Model, Connect, Engage
R-Calculus: A Logical Inference System for Scientific Discovery
Quantum Computing: A Great Science in the Making
The Convergence of Social and Technological Networks
Invited Lectures
Principles of Network Computing
Introduction
Graph Property Test
Homophily of Networks
Homophily Law - The Source of Small Community Phenomenon
Homophily Model and Homophily Theorem
Proof Sketch of Homophily Theorem
Applications in Information Extraction
Conclusions
References
The Small Community Phenomenon in Networks: Models, Algorithms and Applications
Introduction
Basic Definitions and Algorithms
Definition of Community
The Small Community Phenomenon
Community Detection Algorithm
Results on Classical Network Models
Two New Models
Empirical Results
Applications
Classification of Networks
Core Extraction of Networks
References
Vertex-Pursuit in Hierarchical Social Networks
Introduction
Definitions
Random DAG Model
Main Results
Random Regular DAGs
Random Power Law DAGs
Proof of Theorem 1 (v)
Conclusions and Future Work
References
A Structural Approach to Prophecy Variables
Introduction
The Language
The Program Logic
Reasoning about Future Blocks
Auxiliary Code Erasure
Example
The RDCSS Algorithm
Proofs
References
An Assume/Guarantee Based Compositional Calculus for Hybrid CSP
Introduction
Hybrid CSP
History Formulas
Specification and Inference Rules
Discussions, Conclusion and Future Work
References
Automatic Verification of Real-Time Systems with Rich Data: An Overview
Introduction
Overview of the Project R1
Explicit Durations
Structural Optimization
Automating Verification
Complex Data
Verification Tools
Case Studies
Conclusion
References
Program Analysis Using Quantifier-Elimination Heuristics
Introduction
Overview of Quantifier-Elimination Approach
Octagonal Constraints
A Geometric Heuristic for Quantifier-Elimination over Octagonal Constraints
Local Reasoning
Program Analysis Using Octagonal Invariants
Generating Strongest Octagonal Invariants
Towards Disjunctive Invariants: Max Plus Constraints
Concluding Remarks and Future Work
References
Electron Tomography and Multiscale Biology
Electron Tomography
Steps in Electron Tomography
Problems with Electron Tomography
The Mathematics of Electron Tomography
Classical Beam Model
Integral Geometry and the Generalized Radon Transform
Alignment
The Reconstruction Process
Inversion in TxBR
Artifact Reduction for Improved Reconstruction
The Computational Problems Associated with Structural and Systems Biology
Serial Section and Montaging
Processing Requirements
Parallel Processing Approaches
Conclusions: Toward Exascale Computing
References
Contributed Papers
Constant-Time Approximation Algorithms for the Knapsack Problem
Introduction
Definitions
A Constant-Time Algorithm for the Knapsack Problem
Overview of the Algorithm
The Construction of "0365X
Relation between z(X) and z("0365X)
The Algorithm and Its Analysis
Proof of Lemma 3
Lower Bounds
References
Lower Bounds of Shortest Vector Lengths in Random NTRU Lattices
Introduction
Preliminaries
Lattices
Number of Integral Points in a Sphere
Kolmogorov Complexity
The Main Theorem
The Lower Bounds of Shortest Vectors Lengths of NTRU Lattices
Description of the NTRU Cryptosystem
A Technical Lemma
The Lower Bounds of Lengths of Shortest Vectors of NTRU Lattices
Conclusion
References
Polynomial Time Construction of Ellipsoidal Approximations of Zonotopes Given by Generator Descriptions
Introduction
Basic Definitions and the Main Theorem
Some Properties of Zonotopes
Sketch of Goffin's Method
The Version for Zonotopes Given by Generator Descriptions
An Initial Ellipsoid
A Lower Bound on Volume
Parallel Cuts
Testing Whether Z Contains a Ball
The Separation Procedure
The Algorithm
Conclusion
References
Hardness and Approximation of the Asynchronous Border Minimization Problem
Introduction
Preliminaries
P-BMP: Finding Embedding When Placement Is Given
BMP: Finding Placement and Embedding
1D-BMP: BMP on a 1D Array
BMP on 2D Array
A O(n14log2n) Approximation Algorithm for the BMP
Concluding Remarks
References
Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics
Introduction
Motivation
Related Work
Main Results and Organization of the Paper
Preliminaries
The Asymptotic Behavior of Sn and S'n
The Asymptotic Behavior of An
Concluding Remarks
References
Computing Bits of Algebraic Numbers
Introduction
Versions of the Problem
Previous Proof Techniques
Our Proof Technique
Related Work and Our Results
Organization of the Paper
Preliminaries
Complexity Theoretic Preliminaries
Mathematical Preliminaries
From Approximation to Exact Computation
Complexity of Composition
Establishing Quadratic Convergence
Putting It All Together
Lower Bound
Conclusion
References
Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms
Introduction
First Results
Using a Better Parameterized Algorithm
Splitting the Clauses
Approximate Pruning of the Search Tree
Splitting the Variables
Discussion
References
Computing Error Distance of Reed-Solomon Codes
Introduction
RelatedWork
Our Results
Preliminaries
Character Sums and theWeil Bound
Li-Wan's New Sieve
Main Theorem and Its Proof
Conclusions
References
Coordination Mechanisms for Selfish Parallel Jobs Scheduling
Introduction
The Model
Our Contribution
Related Works
Preliminaries
The Price of Anarchy of Bottom-Left Based Policies
Upper Bounds for Greedy BLDW
Homogeneous Unequal Clusters
Lower Bounds on the Price of Anarchy
The Price of Anarchy of Shelf-Packing Based Policies
The Price of Anarchy for Clusters with Different Speeds
BLDW Policy in a Heterogeneous Grid with Different Speeds
FFDH Policy in a Heterogeneous Grid with Different Speeds
Convergence of Pure Nash Equilibria
References
Computationally-Fair Group and Identity-Based Key-Exchange
Introduction
Preliminaries
Non-malleably Independent Dominant-Operation Values, and Session-Key Computational Fairness
Re-examination of the Burmester-Desmedet Group Key-Exchange Protocol
Brief Review of the Burmester-Desmedet Group Key-Exchange Protocol
An Attack against the BD-Protocol
Computationally-Fair Group Key-Exchange
Re-examination of the Chen-Kudla Identity-Based Key-Exchange Protocol
Brief Review of the Chen-Kudla Identity-Based Key-Exchange Protocol
An Attack on the CK-protocol for =
Computational Fair Identity-Based Key-Exchange
References
Timed Encryption with Application to Deniable Key Exchange
Introduction
Definitions
Timed Encryption
Timed Commitment
Timed Encryption in the Random Oracle Model
Timed Encryption without a Random Oracle
Application to Adaptive Deniable Key Exchange
Construction
Security
References
Online Makespan Scheduling of Linear Deteriorating Jobs on Parallel Machines
Introduction
Preliminaries
Simple Linear Deterioration pj = bj sj
Online-Time Model: Scheduling Jobs with Arbitrary Release Times
Online-List Model: Two Machine Scheduling with Availability Constraint
Online-List Model: Fixed Deteriorating Rate and Varying Normal Processing Time pj = aj + b sj
Lower Bounds
Upper Bounds
Summary and Future Work
References
A Surprisingly Simple Way of Reversing Trace Distance via Entanglement
Introduction
Preliminaries
Quantum Information and Relevant Linear Algebra
Direct Proof
A Retrospect of Our Construction
References
Constructions for Binary Codes Correcting Asymmetric Errors from Function Fields
Introduction
Construction
Examples
References
Stopping Set Distributions of Algebraic Geometry Codes from Elliptic Curves
Introduction
Stopping Set Distributions of AG Codes from Elliptic Curves
Conclusion
References
Energy-Efficient Network Routing with Discrete Cost Functions
Introduction
Related Work
Our Results
The Model
Hardness
Integer Program Formulation
The Approximation Algorithm
Transforming the Program
Two-Step Rounding
Performance Evaluation
Model Extension: Bicriteria Network Routing
Conclusion
References
An Algorithmic View on Multi-Related-Segments: A Unifying Model for Approximate Common Interval
Introduction
Gene Proximity: Properties and Models
Key Properties of Gene Proximity
Existing Models
Multi-Related Segments Model
Complexity Analysis of
Identify a Given A
Identify All When A Is Unknown
References
The Worst Case Behavior of Randomized Gossip
Introduction
Our Results
Other Related Work
Model and Preliminary Results
The List-Based Model
Exponential Gaps
A Polynomial-Time Algorithm for the ``Skip None'' Variant
Inapproximability Results
The Case of Directed Graphs
References
Holographic Algorithms on Domain Size k & 2
Introduction
Background and Some Results about Domain Size 2
Some Background
Some Results on Signatures of Domain Size 2
SRP of Signatures on Domain Size k
Degenerate Recognizers
Simultaneous Realizable Problem on Domain Size k
An Algorithm for Simultaneous Realizability Problem on Domain Size k
Some Examples
References
A Refined Exact Algorithm for Edge Dominating Set
Introduction
Enumeration-Based Algorithms
Branching Rules and Some Structural Properties
The Algorithm
The Analysis
Preliminaries
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Putting All Together
References
Finite Automata over Structures
Introduction
The Automata Model
Simple Properties of S-Automata
The Validation Problem
The Emptiness Problem
Discussion and Future Work
References
Deterministic Distributed Data Aggregation under the SINR Model
Introduction
Our Contribution and Techniques
Related Previous Work
Model and Related Terminologies
Model
Related Terminologies
Data Aggregation Algorithm
Algorithm Overview
Algorithm
Analysis
Conclusions
References
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
Introduction
Preliminaries
Tensors
Strong Quantum Nondeterministic Multiparty Communication
Proof of Theorem 1
A Quantum-Classical Super-Polynomial Separation
Concluding Remarks
References
Speed Scaling Problemswith Memory/Cache Consideration
Introduction
Formulation
Non-cache Model
With-Cache Model
Aligned Jobs in Uniform With-Cache Model
With-Cache Model: Approximation Algorithm for General Jobs with Resource Augmentation
Conclusion
References
On the Amount of Nonconstructivity in Learning Formal Languages from Positive Data
Introduction
Preliminaries
Results
Nonconstructive Learning of Indexable Classes
Nonconstructive Learning of Recursively Enumerable Classes
Conclusions
References
Computing in the Fractal Cloud: Modular Generic Solvers for SAT and Q-SAT Variants
Introduction
Definitions
Computing in the Fractal Cloud
A Modular Q-SAT Solver
Setting Up the Decision Tree
Compiling the Formula
Aggregating the Results
Machines for SAT Variants
Complexities
Conclusion
References
Online Optimization of Busy Time on Parallel Machines
Introduction
Notations and Preliminaries
Cost Minimization-MinBusy Problem
General Instances
One-Sided Clique Instances
Clique Instances
Throughput Maximization-MaxThroughput Problem
Basic Results
Lower Bounds for Feasible One-Sided Clique Instances
Online Algorithm for Feasible One-Sided Clique Instances
Summary and Future Work
References
Bisection (Band)Width of Product Networks with Application to Data Centers
Introduction
Definitions
Bounds on the Bisection Width of Product Graphs
Bisection Width of Products of Paths and CBT
Products of Rings and Extended Trees
BCube
References
Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations
Introduction
Preliminaries
Implicit Algorithms for Maximum Bipartite Matchings
References
A Game-Theoretic Approach for Balancing the Tradeoffs between Data Availability and Query Delay in Multi-hop Cellular Networks
Introduction
Problem Formulations
The Design of Caching Payment Mechanism
Data Caching Game
Simulation Experiments
The Simulation Model and System Parameters
Simulation Results
Conclusion
References
Proving Liveness Property under Strengthened Compassion Requirements
Introduction
Computational Model
Discrete Transition Systems
Fair Discrete Systems
A Discussion on Different Kinds of Fairness
Proving Properties
Proof Rule
Soundness of the Rule
Relative Completeness of the Rule
Dealing with Systems with Infinite Number of States
Concluding Remarks
References
Realizing Monads in Interaction Nets via Generic Typed Rules
Introduction
Preliminaries
Interaction Nets
Side Effects, Monads and Generic Rules
Generic Rules and Imposed Constraints
Generic Rules
Generic Rules with Variadic Agents
A Simple Typing Approach
Our Typing Approach
Typing for the Variadic Agent Case
Application: Monads in Interaction Nets
Conclusion and Related Work
References
Towards an Axiomatization of Simple Analog Algorithms
Introduction
Dynamical Transition Systems
Signals
Transition Systems
Abstract Dynamical Systems
Abstract States
Locations in States
Updates of States
Algorithmic Dynamic Systems
Algorithmicity
Flows and Jumps
Analgorithms
Properties
Further Considerations
Programs
Definition
Semantics
Examples
Discussion
References
Multiple Usage of Random Bits in Finite Automata
Introduction
Preliminary Results
Main Results
References
Minimum Certificate Dispersal with Tree Structures
Introduction
Minimum Certificate Dispersal Problem
MCD for Star Request Sets
MCD for Tree Request Sets
Tree Structure with Arbitrary Degree
Tree Structure with O(logn) Degree
Tree Structures with Constant Degree
MCD for Tree Graphs
Basic Idea of Polynomial Time Solvability
A Faster Computation
Concluding Remarks
References
Improved FPT Algorithms for Rectilinear k-Links Spanning Path
Introduction
Rectilinear k-Links Spanning Path in 2-Dimensions Is Hard
FPT Algorithms for Rectilinear k-Links Spanning Path
FPT Algorithm Based on Branching and Dynamic Programming
Improved Algorithm in 2-Dimensions
Rectilinear k-Bends TSP
Conclusion
References
FPT Results for Signed Domination
Introduction
Preliminaries
Signed Dominating Set in General Graph
Signed Dominating Set on Planar Graph
Linear Kernel for Signed Dominating Set
FPT Algorithm for Signed Dominating Set
Signed Dominating Set in Special Graph
Polynomial Kernel in Bipartite Graph
Linear Kernel in d Graph
Linear Kernel in r-Regular Graph
Conclusion
References
Submodular Minimization via Pathwidth
Introduction
Preliminaries
Pruning in Search Tree for Pathwidth
A Search Tree Algorithm
References
A Detailed Study of the Dominating Cliques Phase Transition in Random Graphs
Introduction
Preliminary Results
Proofs of Theorems
Proof of Theorem 1
Proof of Theorem 2
Conclusions
References
An Application of 1-Genericity in the ?02 Enumeration Degrees
Introduction
Preliminaries
The Main Construction
Enumeration 1-Genericity
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken