Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi’an, China, April 25-29, 2008. Proceedings

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 -