This book constitutes the refereed proceedings of the 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008, held in Xi'an, China in April 2008.
The 48 revised full papers presented together with 2 invited talks and 1 plenary lecture were carefully reviewed and selected from 192 submissions. The papers address current issues of all major areas in computer science, mathematics (especially logic) and the physical sciences - computation, algorithms, complexity and computability theory in particular. With this crossdisciplinary character the conference is given a special flavor and distinction.
Author(s): Cynthia Dwork (auth.), Manindra Agrawal, Dingzhu Du, Zhenhua Duan, Angsheng Li (eds.)
Series: Lecture Notes in Computer Science 4978 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2008
Language: English
Pages: 598
Tags: Theory of Computation; Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Computing Methodologies; Mathematics of Computing; Computational Biology/Bioinformatics
Front Matter....Pages -
Differential Privacy: A Survey of Results....Pages 1-19
On the Complexity of Measurement in Classical Physics....Pages 20-30
Quantum Walk Based Search Algorithms....Pages 31-46
Propositional Projection Temporal Logic, B $\ddot{u}$ chi Automata and ω -Regular Expressions....Pages 47-58
Genome Rearrangement Algorithms for Unsigned Permutations with O (log n ) Singletons....Pages 59-69
On the Complexity of the Hidden Subgroup Problem....Pages 70-81
An O * (3.52 3k ) Parameterized Algorithm for 3-Set Packing....Pages 82-93
Indistinguishability and First-Order Logic....Pages 94-104
Derandomizing Graph Tests for Homomorphism....Pages 105-115
Definable Filters in the Structure of Bounded Turing Reductions....Pages 116-124
Distance Constrained Labelings of Trees....Pages 125-135
A Characterization of NC k by First Order Functional Programs....Pages 136-147
The Structure of Detour Degrees....Pages 148-159
Hamiltonicity of Matching Composition Networks with Conditional Edge Faults....Pages 160-169
Local 7-Coloring for Planar Subgraphs of Unit Disk Graphs....Pages 170-181
Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity....Pages 182-191
More on Weak Bisimilarity of Normed Basic Parallel Processes....Pages 192-203
Extensions of Embeddings in the Computably Enumerable Degrees....Pages 204-211
An Improved Parameterized Algorithm for a Generalized Matching Problem....Pages 212-222
Deterministic Hot-Potato Permutation Routing on the Mesh and the Torus....Pages 223-233
Efficient Algorithms for Model-Based Motif Discovery from Multiple Sequences....Pages 234-245
Ratio Based Stable In-Place Merging....Pages 246-257
A Characterisation of the Relations Definable in Presburger Arithmetic....Pages 258-269
Finding Minimum 3-Way Cuts in Hypergraphs....Pages 270-281
Inapproximability of Maximum Weighted Edge Biclique and Its Applications....Pages 282-293
Symbolic Algorithm Analysis of Rectangular Hybrid Systems....Pages 294-305
On the OBDD Complexity of the Most Significant Bit of Integer Multiplication....Pages 306-317
Logical Closure Properties of Propositional Proof Systems....Pages 318-329
Graphs of Linear Clique-Width at Most 3....Pages 330-341
A Well-Mixed Function with Circuit Complexity 5 n ± o ( n ): Tightness of the Lachish-Raz-Type Bounds....Pages 342-350
A Logic for Distributed Higher Order π -Calculus....Pages 351-363
Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs....Pages 364-374
A Topological Study of Tilings....Pages 375-387
A Denotational Semantics for Total Correctness of Sequential Exact Real Programs....Pages 388-399
Weak Bisimulations for the Giry Monad (Extended Abstract)....Pages 400-409
Approximating Border Length for DNA Microarray Synthesis....Pages 410-422
On a Question of Frank Stephan....Pages 423-432
A Practical Parameterized Algorithm for the Individual Haplotyping Problem MLF....Pages 433-444
Improved Algorithms for Bicluster Editing....Pages 445-456
Generation Complexity Versus Distinction Complexity....Pages 457-466
Balancing Traffic Load Using One-Turn Rectilinear Routing....Pages 467-478
A Moderately Exponential Time Algorithm for Full Degree Spanning Tree....Pages 479-489
Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems....Pages 490-501
A Linear-Time Algorithm for Finding All Door Locations That Make a Room Searchable....Pages 502-513
Model Theoretic Complexity of Automatic Structures (Extended Abstract)....Pages 514-525
A Separation between Divergence and Holevo Information for Ensembles....Pages 526-541
Unary Automatic Graphs: An Algorithmic Perspective....Pages 542-553
Search Space Reductions for Nearest-Neighbor Queries....Pages 554-567
Total Degrees and Nonsplitting Properties of $\Sigma_2^0$ Enumeration Degrees....Pages 568-578
s-Degrees within e-Degrees....Pages 579-587
The Non-isolating Degrees Are Upwards Dense in the Computably Enumerable Degrees....Pages 588-596
Back Matter....Pages -
