Theory and Applications of Models of Computation
9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings
Published on 4. May 2012
XV, 622 pages
978-3-642-29952-0 (ISBN)
Description
This book constitutes the refereed proceedings of the 9th International Conference on Theory and Applications of Models of Computation, TAMC 2012, held in Beijing, China, in May 2012. The conference was combined with the Turing Lectures 2012, dedicated to celebrating Alan Turing's unique impact on mathematics, computing, computer science, informatics, morphogenesis, philosophy, and the wider scientific world. Eight Turing Lectures were given at the TAMC 2012.
The 40 revised full papers presented together with invited talks were carefully reviewed and selected from 86 submissions. The papers address 4 special sessions at TAMC 2012 which were algorithms and information in networks, complexity and cryptography, models of computing and networking, programming and verification.
More details
Other editions
Additional editions
Manindra Agrawal | Barry S. Cooper | Angsheng Li
Theory and Applications of Models of Computation
9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings
Book
05/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- 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
