Theory and Applications of Models of Computation: 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings

Front Matter....Pages -
On the Impact of Turing Machines....Pages 1-2
From Turing Machine to Morphogenesis: Forming and Informing Computation....Pages 3-10
Theory of Computation as an Enabling Tool for the Sciences....Pages 11-11
Interaction and Collective Intelligence on the Internet....Pages 12-22
What Computers Do: Model, Connect, Engage....Pages 23-26
R-Calculus: A Logical Inference System for Scientific Discovery....Pages 27-27
Quantum Computing: A Great Science in the Making....Pages 28-28
The Convergence of Social and Technological Networks....Pages 29-29
Principles of Network Computing....Pages 30-39
The Small Community Phenomenon in Networks: Models, Algorithms and Applications....Pages 40-49
Vertex-Pursuit in Hierarchical Social Networks....Pages 50-60
A Structural Approach to Prophecy Variables....Pages 61-71
An Assume/Guarantee Based Compositional Calculus for Hybrid CSP....Pages 72-83
Automatic Verification of Real-Time Systems with Rich Data: An Overview....Pages 84-93
Program Analysis Using Quantifier-Elimination Heuristics....Pages 94-108
Electron Tomography and Multiscale Biology....Pages 109-130
Constant-Time Approximation Algorithms for the Knapsack Problem....Pages 131-142
Lower Bounds of Shortest Vector Lengths in Random NTRU Lattices....Pages 143-155
Polynomial Time Construction of Ellipsoidal Approximations of Zonotopes Given by Generator Descriptions....Pages 156-163
Hardness and Approximation of the Asynchronous Border Minimization Problem....Pages 164-176
Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics....Pages 177-188
Computing Bits of Algebraic Numbers....Pages 189-201
Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms....Pages 202-213
Computing Error Distance of Reed-Solomon Codes....Pages 214-224
Coordination Mechanisms for Selfish Parallel Jobs Scheduling....Pages 225-236
Computationally-Fair Group and Identity-Based Key-Exchange....Pages 237-247
Timed Encryption with Application to Deniable Key Exchange....Pages 248-259
Online Makespan Scheduling of Linear Deteriorating Jobs on Parallel Machines....Pages 260-272
A Surprisingly Simple Way of Reversing Trace Distance via Entanglement....Pages 273-283
Constructions for Binary Codes Correcting Asymmetric Errors from Function Fields....Pages 284-294
Stopping Set Distributions of Algebraic Geometry Codes from Elliptic Curves....Pages 295-306
Energy-Efficient Network Routing with Discrete Cost Functions....Pages 307-318
An Algorithmic View on Multi-Related-Segments: A Unifying Model for Approximate Common Interval....Pages 319-329
The Worst Case Behavior of Randomized Gossip....Pages 330-345
Holographic Algorithms on Domain Size k  > 2....Pages 346-359
A Refined Exact Algorithm for Edge Dominating Set....Pages 360-372
Finite Automata over Structures....Pages 373-384
Deterministic Distributed Data Aggregation under the SINR Model....Pages 385-399
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication....Pages 400-411
Speed Scaling Problems with Memory/Cache Consideration....Pages 412-422
On the Amount of Nonconstructivity in Learning Formal Languages from Positive Data....Pages 423-434
Computing in the Fractal Cloud: Modular Generic Solvers for SAT and Q-SAT Variants....Pages 435-447
Online Optimization of Busy Time on Parallel Machines....Pages 448-460
Bisection (Band)Width of Product Networks with Application to Data Centers....Pages 461-472
Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations....Pages 473-486
A Game-Theoretic Approach for Balancing the Tradeoffs between Data Availability and Query Delay in Multi-hop Cellular Networks....Pages 487-497
Proving Liveness Property under Strengthened Compassion Requirements....Pages 498-508
Realizing Monads in Interaction Nets via Generic Typed Rules....Pages 509-524
Towards an Axiomatization of Simple Analog Algorithms....Pages 525-536
Multiple Usage of Random Bits in Finite Automata....Pages 537-547
Minimum Certificate Dispersal with Tree Structures....Pages 548-559
Improved FPT Algorithms for Rectilinear k -Links Spanning Path....Pages 560-571
FPT Results for Signed Domination....Pages 572-583
Submodular Minimization via Pathwidth....Pages 584-593
A Detailed Study of the Dominating Cliques Phase Transition in Random Graphs....Pages 594-603
An Application of 1-Genericity in the $\\Pi^0_2$ Enumeration Degrees....Pages 604-620
Back Matter....Pages -