Theory and Applications of Models of Computation: 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings (Lecture Notes in Computer Science, 4484)

This book constitutes the refereed proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. It addresses all major areas in computer science; mathematics, especially logic; and the physical sciences, particularly with regard to computation and computability theory. The papers particularly focus on algorithms, complexity and computability theory. Title Preface Organization Table of Contents Detecting Sharp Drops in PageRank and aSimplified Local Partitioning Algorithm Introduction Preliminaries Approximate Personalized PageRank Vectors A Sharp Drop in PageRank Implies a Good Cut Ensuring That a Sharp Drop Exists Local Partitioning Algorithm Generalizations of the Compactness Theorem and G ̈odel’s Completeness Theorem for Nonstandard Finite Structures Introduction The Formulation of the Results Connection with Complexity Theory Set Theory Finite Set Theory Standard and Nonstandard Sets First-Order Formulas Extensions of Interpretations First-Order Definability Compactness Theorem First-Order Definability of Sets Sequences The Proof of the Compactness Theorem The Completeness Theorem Proofs in LK Diagrams, and Induction Axioms The Statement of the Completeness Theorem The Sketch of the Proof of the Completeness Theorem Approximation Algorithms for 3D Orthogonal Knapsack Introduction An Algorithm Based on Strip Packing A Refined Construction Enumerations and a Shifting Technique Conclusion A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences Introduction Modified Yehuda-Fogel Algorithm Average Performance A Closer Look at Greedy Algorithm Concluding Remarks The Hardness of Selective Network Design for Bottleneck Routing Games Introduction Preliminaries Main Results A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns Introduction Interval Graph Patterns Interval Graph Pattern Matching Minimally Generalized Linear Interval Graph Patterns Conclusions and Future Work Elementary Differences Among Jump Hierarchies Introduction Requirements and Strategies The Priority Tree $T$ Working with the LR Degrees Introduction Oracle Martin-Löf Tests $LR$ Reducibility and Degrees Global Structure Computably Enumerable $LR$ Degrees Computability on Subsets of Locally Compact Spaces Introduction Preliminaries Type-2 Theory of Effectivity (TTE) Representations of Points and Sets in Computable $\T_0$-Spaces Effectivity in Locally Compact Hausdorff Spaces Computability on Subsets of Computably Locally Compact, Computably Hausdorff Spaces Computability on Closed Subsets Computability on Compact Subsets Conclusion and Future Work Appendix: Proofs A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs Introduction Preliminaries Open and Closed Prefix Trees and Basic Operation Canonical Trees Linear Time Construction of Canonical Trees Applications Finding a Duplicate and a Missing Item in a Stream Introduction Simple Algorithms Limitations of Multiple-Pass Streaming Algorithms The Minimum Space Required for One-Pass Algorithms One-Pass Las-Vegas Randomized Algorithms Open Problems and Discussions Directed Searching Digraphs: Monotonicity and Complexity Introduction Monotonicity of the Mixed Directed Search Model Monotonicity of the Directed Search Model NP-Completeness Results Conclusion Protecting Against Key Escrow and Key Exposure in Identity-Based Cryptosystem Introduction Background Related Work Our Contribution Preliminaries Our Key Issuing and Updating Model Entities Involved Framework and Security Model Our Proposed Encryption Scheme The IBKIUE Scheme Correctness Analysis and Comparison Security Analysis Our Proposed Signature Scheme The IBKIUS Scheme Security Analysis Conclusion References Encapsulated Scalar Multiplications and Line Functions in the Computation of Tate Pairing Introduction Preliminaries Computation of Miller's Paths Miller's Path to 4T Miller's Path to $2T\pm P$ Miller's Path to $3T$ Miller's Path to $6T$ Miller's Path to $iT\pm P$ for $i=3,4,6$. Example Conclusion A Provably Secure Blind Signature Scheme Instruction Preliminaries The Proposed Scheme Security Proofs Conclusions Construct Public Key Encryption Scheme Using Ergodic Matrices over GF(2) Introduction Ergodic Matrices over Finite Field $\F_2$ New Public Key Encryption System Hard Problem Public Key Encryption Scheme Example Conclusions New Left-to-Right Radix-r Signed-Digit Recoding Algorithm for Pairing-Based Cryptosystems Introduction Preliminaries Notations Radix-$r$ Signed-Digit Number Representations Left-to-Right Recoding Algorithm and Its Application in ECC New Left-to-Right Radix-$r$ Signed-Digit Recoding Algorithm The Basic Idea of Our Algorithm The Proposed Algorithm Analysis and Comparison Analysis Comparison Conclusion The Strongest Nonsplitting Theorem Introduction Requirements and Strategies The Naive $N_{\Psi}$-Strategy The Naive $P_{\Theta}$-Strategy $N_{\Psi}$ Below $P_{\Theta}$ The Approximations The Basic Module for One $\ptheta$- and One $\npsi$- Requirement All Requirements There is an Sw-Cuppable Strongly c.e. Real Introduction A Corollary Procedure $\P(n,k)$ Proof of Theorem 1.6 References On Computation Complexity of the Concurrently Enabled Transition Set Problem Introduction Basic Definitions Petri Nets Concurrently Enabled Transition Set Computational Complexity Independent Set Problem Concurrently Enabled Transition Set Problem Maximal Concurrently Enabled Transition Set Problem Subproblem Analysis Conclusions Synchronization of Some DFA Introduction Preliminaries The Graph $\Gamma^2$ Transition Semigroup of Automaton The State Outside $t$-Cycle Aperiodic Strongly Connected DFA The General Case of Aperiodic DFA On the Treewidth and Pathwidth of Biconvex Bipartite Graphs Introduction Bipartite Permutation Graphs Biclique Structure Computing Treewidth in Linear Time Biconvex Bipartite Graphs Biclique Structure Treewidth and Pathwidth On Exact Complexity of Subgraph Homeomorphism Introduction Walks and Sets of Walks An Exact Algorithm for Fixed-Vertex Homeomorphism A Faster Algorithm for Fixed-Vertex Homeomorphism Exact Algorithms for Subgraph Homeomorphism Final Remarks Searching a Polygonal Region by Two Guards Introduction Preliminary Basic Definitions Two-Guard Searchability of Corridors Necessary Conditions Sufficiency The Search Schedule for Case 1 The Search Schedule for Case 2 On the Internal Steiner Tree Problem Introduction Preliminaries MAX SNP-Hardness Result An Approximation Algorithm Concluding Remarks Approximately Optimal Trees for Group Key Management with Batch Updates Introduction Preliminaries Lower Bound for Optimal Tree Cost as $p \to 0$ Heuristic LR and Its Approximation Ratio Heuristic LB and Its Approximation Ratio Conclusions On Deciding Deep Holes of Reed-Solomon Codes Introduction Related Work Our Results A Simple Proof That the Maximum Likelihood Decoding Is NP-Complete A Hypersurface Related to Deep Holes A Smooth Curve Estimation of Number of Rational Points Concluding Remarks Quantum Multiparty Communication Complexity and Circuit Lower Bounds Introduction Multiparty Communication Complexity and Circuit Lower Bounds Quantum Multiparty Communication Complexity Simulating Classical Players A Quantum Reduction for Circuit Lower Bounds The Quantum Communication Complexity of GIP Efficient Computation of Algebraic Immunity of Symmetric Boolean Functions Introduction General Observation for $f\in SB_{n}$ with $AI_{n}(f)\geq d$ Computing Algebraic Immunity of a Given Symmetric Boolean Function Searching All Symmetric Boolean Functions with Algebraic Immunity $\geq$ d Our Experiments and Conclusions Improving the Average Delay of Sorting Introduction Timing of a Boolean Circuit Average Case Efficient Comparator Modules Average Case Delay for the Uniform Distribution Average Case Delay for Nonuniform Distributions Conclusion Approximating Capacitated Tree-Routings in Networks Introduction Preliminaries Tree Cover Approximation Algorithm to CTR Conclusion Feedback Arc Set Problem in Bipartite Tournaments Introduction Randomized Algorithm for FAS Deterministic Algorithm for FAS Conclusion Studying on Economic-Inspired Mechanisms for Routing and Forwarding in Wireless Ad Hoc Network Introduction System Models Cost Model Concepts in Mechanism Design Hidden Information and Routing Mechanisms Hidden Actions in Message Forwarding Conclusion and Future Works References Enhancing Simulation for Checking Language Containment Introduction Preliminaries Search Pairs of States for Language Containment Construct New Büchi Automaton Comparison Conclusion QBF-Based Symbolic Model Checking for Knowledge and Time Introduction Quantified Boolean Formula Interpreted System Semantics Computation Tree Logic of Knowledge-CTLK Bounded Semantics of CTLK The BMC Algorithm for CTLK The Correctness of the Translation Summary A Characterization of the Language Classes Learnable with Correction Queries Introduction Preliminaries Query Learning Gold-Style Learning Characterization of the Class $\CorQ^(A)$ Relations to Other Learning Models A Model Included in $CorQ$ A Model Which Includes $CorQ^(A)$ Concluding Remarks Learnable Algorithm on the Continuum Introduction Limiting Recursion Learnable Real Numbers Learnable Sequences of Real Numbers Online Deadline Scheduling with Bounded Energy Efficiency Introduction Preliminaries Relaxed Energy Efficiency Threshold The Online Algorithm Performance of $\Efficiency_{E/(1+\epsilon)}$ Randomized Algorithm Performance of the Randomized Algorithm Comparing Non-preemptive and Preemptive Optimal Schedules at Fixed Speed Without Demanding Jobs Efficient Algorithms for Airline Problem Introduction Minimum Cost Network Minimum Cost Spanning Tree $NP$-Hardness for Finding a Spanning Tree of Minimum Loss Approximation Algorithms for a Tree Airline Network Concluding Remarks and Acknowledgment Efficient Exact Arithmetic over Constructive Reals Introduction Basic Definitions and Algorithms Problems Addition Algorithm with Balanced Precision Algorithm with Precision Control Conclusions and Discussions Bounding Run-Times of Local Adiabatic Algorithms Introduction Preliminaries Perturbed Unordered Search The Bounds Global Evolution Local Evolution Conclusions A Note on Universal Composable Zero Knowledge in Common Reference String Model Introduction Related Works Preliminaries Concurrent General Composition Attack on UCZK in the Common Reference String Model The Protocol Structure of UCZK of [18] The CGC Attack Comments A Note on the Feasibility of Generalized Universal Composability (Extended Abstract) Introduction Preliminaries On the Hardness of Achieving Generalized UC The UCZK Protocol Implied by [8,9,11] A Simple State-Information-Sharing Attack Comments and Discussion Fixing Suggestion with Source/Session-Authentic Commitments t-Private and Secure Auctions Introduction Notation and Preliminaries $t$-Private Garbled Circuit Construction Security Against Active Attacks Dynamic $t$-Private Auctions Conclusions Secure Multiparty Computations Using a Dial Lock (Extended Abstract) Introduction Dial Locks Secure Multiparty Computations Our Results Secure Computations Using Dial Locks An Example Our Protocols Abstraction A Necessary Condition for Dial-Computable Functions Characterizing Symmetric Dial-Computable Functions Conclusions A Time Hierarchy Theorem for Nondeterministic Cellular Automata Introduction Nondeterministic Cellular Automata Time Hierarchy for Nondeterministic CA Universal CA Recursive Padding Recursively Padding CA and Their Languages Proof of Theorem 1 Conclusion and Final Observations Decidability of Propositional Projection Temporal Logic with Infinite Models Introduction Propositional Projection Temporal Logic Normal Form of PPTL Normal Form Graph Definition of NFG Algorithm for Constructing NFG Finiteness of NFG Decision Procedure for PPTL Formulas Path and Satisfiability Decision Procedure Conclusion Separation of Data Via Concurrently Determined Discriminant Functions Introduction Model Development Experiments with Six Well-Studied Datasets Conclusion The Undecidability of the Generalized Collatz Problem Introduction Conway's Reduction Reducing a Counter Machine to a FracTran Program Reducing FracTran to GCP Improvements to Conway's Reduction Universal Totality Unintended Factors Our Main Result Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces Introduction Graphs and Geometry Metric Spaces and Doubling Dimension Nearest Neighbor Graphs Graph Partitioning and Vertex Separators Laplacian and the Fiedler Value Singular Value Decomposition A Separator Theorem for Doubling Dimensional Spaces Shallow Minors Proof of Theorem 2 A Spectral Theorem for Nearly-Euclidean Spaces Conclusion Maximum Edge-Disjoint Paths Problem in Planar Graphs Introduction Maximum Edge-Disjoint Paths Problem #P-Hardness An Efficient Algorithm for Generating Colored Outerplanar Graphs Introduction Preliminaries The Family Tree of Left-Heavy Outerplane Graphs Left-Heavy Outerplane Graphs The Family Tree Algorithm Generating Graphs by Adding a Type 1 or Type 2 Block Generating Children Graphs by Adding an Inner Edge Conclusion Orthogonal Drawings for Plane Graphs with Specified Face Areas Introduction Preliminary Drawings of Slicing Graphs Combined Decagon Outline of Algorithm Drawing of Rectangular Graphs Drawing of 3-Connected Plane Graph Conclusion Absolutely Non-effective Predicates and Functions in Computable Analysis Introduction Concepts from Computable Analysis Absolutely Non-open Sets Applications to Computable Measure Theory Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic Binary Sequences Introduction and Summary Component Circuits/Networks Inverting the Inputs of a Comparator Network The Beals-Nishino-Tanaka Inverter Conditional Shifter Negation-Limited $k$-Tonic Inverter Overall Structure of the $k$-Tonic Inverter Reducing the Depth to $O(\log k \log\log n)$ Reducing the Number of NOTs Negation-Limited $k$-Tonic Sorter Open Problems The Existence of Unsatisfiable Formulas in k-LCNF for k ≥ 3 Introduction Minimal Unsatisfiable Formulas and Its Applications Construction of Linear Minimal Unsatisfiable Formulas Conclusions and Future Works Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model Introduction A Glimpse on the BT Model A Description of the BT Model Lower Bound Strategies for the BT Model Improving Lower Bounds of Knapsack Lower Bound of Exact Algorithms Lower Bound of Approximation Algorithms Discussion Phase Transition of Multivariate PolynomialSystems Introduction Related Work Probability of No Solutions and of Exactly $s$ Solutions Extension of the Results to $\mathbb{Z}/(pq)$ Experimental Results Linearly Independent Equations Sparse Systems Equations from Cryptographic Systems Conclusions and Open Problems Approximation Algorithms for Maximum Edge Coloring Problem Introduction Problem Definition Motivation Preliminaries Approximation Algorithms for Case $q=2$ Approximation Algorithms for Case $q>2$ Conclusion Two Improved Range-Efficient Algorithms for F_0 Estimation Introduction Preliminaries Algorithm for Range-Efficient $F_0$ Estimation Extension: Max-Dominance Norm Problem Further Work Approximation to the Minimum Rooted Star Cover Problem Introduction Hardness Minimum Rooted Star Cover Minimum Rooted Star Cover Minimum Rooted Star Cover Better Approximation Discussion Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems Introduction Preliminaries Hardness Results $(*,\Delta)$-Matrices $(*, 2)$- and $(2, *)$-Matrices Future Work Parameterized Algorithms for Weighted Matching and Packing Problems Introduction Preliminaries An Algorithm for Weighted $m-set Packing$ An Algorithm for Weighted $m-d Matching$ Conclusions Kernelizations for Parameterized Counting Problems Introduction Definitions and the Concept of Counting Kernelizations Counting Kernelization $p$-#VertexCover and $p$-Card-#Hittingset Crown Rule Reduction for $p$-#VertexCover A Kernelization for $p$-#UniqueHittingSet Characterizing FFPT by Counting Kernelizations Concluding Remarks Revisiting the Impossibility for Boosting Service Resilience Introduction Background Problem Addressed Related Work Our Contribution Organization Preliminaries Sequential Types, Atomic Objects, and Services Shared Variable Systems with Services The Implementation of Consensus Objects Impossibility for Infinite Systems A Brief Review A Generalization to the Case of Infinite Systems Impossibility for Systems with Shared Variables Impossibility and the Idea for Its Proof The Construction of a Simulating System A Property of $T(C)$ Conclusion An Approximation Algorithm to the k-Steiner Forest Problem Introduction Our Results and Techniques The Coupling Greedy Algorithm for Set $k$-Cover Approximating $k$-Steiner Forest Find Cost-Effective Covering Tree The Greedy Algorithm for $k$-Steiner Forest Discussion A Distributed Algorithm of Fault Recovery for Stateful Failover Introduction High Availability Framework for $k$-Fault Tolerance Network and Fault Model Framework Automated Fault Recovery Distributed Algorithm Analysis of the Algorithm Formal Verification of the Distributed Algorithm Conclusion Appendix Harary Graph Path Embedding on Folded Hypercubes Introduction Preliminaries Three Edge-Fault-Tolerant Properties Edge-Fault-Tolerant Hamiltonian-Connectivity Edge-Fault-Tolerant Hyper Hamiltonian-Laceability Concluding Remarks An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs Introduction Approximation Algorithms for the Min-CVCB Problem Related Definitions and Lemmas The AACI-D Algorithm Putting All Together Conclusions Author Index This book constitutes the refereed proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. The 67 revised full papers presented together with 2 plenary lectures were carefully reviewed and selected from over 500 submissions. All major areas in computer science, mathematics (especially logic) and the physical sciences particularly with regard to computation and computability theory are addressed. The papers - featuring this crossdisciplinary character - particularly focus on algorithms, complexity and computability theory, giving the conference a special flavor and distinction