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 two plenary lectures were carefully reviewed and selected from over 500 submissions. 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–-featuring this crossdisciplinary character-–particularly focus on algorithms, complexity and computability theory, giving the conference a special flavor and distinction.
Author(s): Reid Andersen, Fan Chung (auth.), Jin-Yi Cai, S. Barry Cooper, Hong Zhu (eds.)
Series: Lecture Notes in Computer Science 4484 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2007
Language: English
Pages: 772
Tags: Theory of Computation; Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Computing Methodologies; Mathematics of Computing; Bioinformatics
Front Matter....Pages -
Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm....Pages 1-12
Generalizations of the Compactness Theorem and Gödel’s Completeness Theorem for Nonstandard Finite Structures....Pages 13-33
Approximation Algorithms for 3D Orthogonal Knapsack....Pages 34-45
A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences....Pages 46-57
The Hardness of Selective Network Design for Bottleneck Routing Games....Pages 58-66
A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns....Pages 67-78
Elementary Differences Among Jump Hierarchies....Pages 79-88
Working with the LR Degrees....Pages 89-99
Computability on Subsets of Locally Compact Spaces....Pages 100-114
A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs....Pages 115-127
Finding a Duplicate and a Missing Item in a Stream....Pages 128-135
Directed Searching Digraphs: Monotonicity and Complexity....Pages 136-147
Protecting Against Key Escrow and Key Exposure in Identity-Based Cryptosystem....Pages 148-158
Encapsulated Scalar Multiplications and Line Functions in the Computation of Tate Pairing....Pages 159-170
A Provably Secure Blind Signature Scheme....Pages 171-180
Construct Public Key Encryption Scheme Using Ergodic Matrices over GF(2)....Pages 181-188
New Left-to-Right Radix- r Signed-Digit Recoding Algorithm for Pairing-Based Cryptosystems....Pages 189-198
The Strongest Nonsplitting Theorem....Pages 199-211
There is an Sw-Cuppable Strongly c.e. Real....Pages 212-221
On Computation Complexity of the Concurrently Enabled Transition Set Problem....Pages 222-233
Synchronization of Some DFA....Pages 234-243
On the Treewidth and Pathwidth of Biconvex Bipartite Graphs....Pages 244-255
On Exact Complexity of Subgraph Homeomorphism....Pages 256-261
Searching a Polygonal Region by Two Guards....Pages 262-273
On the Internal Steiner Tree Problem....Pages 274-283
Approximately Optimal Trees for Group Key Management with Batch Updates....Pages 284-295
On Deciding Deep Holes of Reed-Solomon Codes....Pages 296-305
Quantum Multiparty Communication Complexity and Circuit Lower Bounds....Pages 306-317
Efficient Computation of Algebraic Immunity of Symmetric Boolean Functions....Pages 318-329
Improving the Average Delay of Sorting....Pages 330-341
Approximating Capacitated Tree-Routings in Networks....Pages 342-353
Feedback Arc Set Problem in Bipartite Tournaments....Pages 354-361
Studying on Economic-Inspired Mechanisms for Routing and Forwarding in Wireless Ad Hoc Network....Pages 362-373
Enhancing Simulation for Checking Language Containment....Pages 374-385
QBF-Based Symbolic Model Checking for Knowledge and Time....Pages 386-397
A Characterization of the Language Classes Learnable with Correction Queries....Pages 398-407
Learnable Algorithm on the Continuum....Pages 408-415
Online Deadline Scheduling with Bounded Energy Efficiency....Pages 416-427
Efficient Algorithms for Airline Problem....Pages 428-439
Efficient Exact Arithmetic over Constructive Reals....Pages 440-449
Bounding Run-Times of Local Adiabatic Algorithms....Pages 450-461
A Note on Universal Composable Zero Knowledge in Common Reference String Model....Pages 462-473
A Note on the Feasibility of Generalized Universal Composability....Pages 474-485
t -Private and Secure Auctions....Pages 486-498
Secure Multiparty Computations Using a Dial Lock....Pages 499-510
A Time Hierarchy Theorem for Nondeterministic Cellular Automata....Pages 511-520
Decidability of Propositional Projection Temporal Logic with Infinite Models....Pages 521-532
Separation of Data Via Concurrently Determined Discriminant Functions....Pages 533-541
The Undecidability of the Generalized Collatz Problem....Pages 542-553
Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces....Pages 554-565
Maximum Edge-Disjoint Paths Problem in Planar Graphs....Pages 566-572
An Efficient Algorithm for Generating Colored Outerplanar Graphs....Pages 573-583
Orthogonal Drawings for Plane Graphs with Specified Face Areas....Pages 584-594
Absolutely Non-effective Predicates and Functions in Computable Analysis....Pages 595-604
Linear-Size Log-Depth Negation-Limited Inverter for k -Tonic Binary Sequences....Pages 605-615
The Existence of Unsatisfiable Formulas in k -LCNF for k ≥ 3....Pages 616-623
Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model....Pages 624-631
Phase Transition of Multivariate Polynomial Systems....Pages 632-645
Approximation Algorithms for Maximum Edge Coloring Problem....Pages 646-658
Two Improved Range-Efficient Algorithms for F 0 Estimation....Pages 659-669
Approximation to the Minimum Rooted Star Cover Problem....Pages 670-679
Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems....Pages 680-691
Parameterized Algorithms for Weighted Matching and Packing Problems....Pages 692-702
Kernelizations for Parameterized Counting Problems....Pages 703-714
Revisiting the Impossibility for Boosting Service Resilience....Pages 715-727
An Approximation Algorithm to the k -Steiner Forest Problem....Pages 728-737
A Distributed Algorithm of Fault Recovery for Stateful Failover....Pages 738-749
Path Embedding on Folded Hypercubes....Pages 750-759
An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs....Pages 760-769
Back Matter....Pages -
