5. TAMC 2008: Xi'an, China

Plenary Lectures

• Cynthia Dwork:
  Differential Privacy: A Survey of Results. 1-19
  

Special Session Lectures

• Edwin J. Beggs, José Félix Costa, Bruno Loff, John Tucker:
  On the Complexity of Measurement in Classical Physics. 20-30
  
• Miklos Santha:
  Quantum Walk Based Search Algorithms. 31-46
  

Contributed Lectures

• Cong Tian, Zhenhua Duan:
  Propositional Projection Temporal Logic, Bchi Automata and omega-Regular Expressions. 47-58
  
• Xiaowen Lou, Daming Zhu:
  Genome Rearrangement Algorithms for Unsigned Permutations with O(logn) Singletons. 59-69
  
• Stephen A. Fenner, Yong Zhang:
  On the Complexity of the Hidden Subgroup Problem. 70-81
  
• Jianxin Wang, Qilong Feng:
  An O*(3.523k) Parameterized Algorithm for 3-Set Packing. 82-93
  
• Skip Jordan, Thomas Zeugmann:
  Indistinguishability and First-Order Logic. 94-104
  
• Angsheng Li, Linqing Tang:
  Derandomizing Graph Tests for Homomorphism. 105-115
  
• Angsheng Li, Weilin Li, Yicheng Pan, Linqing Tang:
  Definable Filters in the Structure of Bounded Turing Reductions. 116-124
  
• Jirí Fiala, Petr A. Golovach, Jan Kratochvíl:
  Distance Constrained Labelings of Trees. 125-135
  
• Jean-Yves Marion, Romain Péchoux:
  A Characterization of NCk. 136-147
  
• Lars Kristiansen, Paul J. Voda:
  The Structure of Detour Degrees. 148-159
  
• Sun-Yuan Hsieh, Chia-Wei Lee:
  Hamiltonicity of Matching Composition Networks with Conditional Edge Faults. 160-169
  
• Jurek Czyzowicz, Stefan Dobrev, H. González-Aguilar, Rastislav Kralovic, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, Jorge Urrutia:
  Local 7-Coloring for Planar Subgraphs of Unit Disk Graphs. 170-181
  
• Petr A. Golovach, Jan Kratochvíl:
  Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity. 182-191
  
• Haiyan Chen:
  More on Weak Bisimilarity of Normed Basic Parallel Processes. 192-203
  
• Jitai Zhao:
  Extensions of Embeddings in the Computably Enumerable Degrees. 204-211
  
• Jianxin Wang, Dan Ning, Qilong Feng, Jianer Chen:
  An Improved Parameterized Algorithm for a Generalized Matching Problem. 212-222
  
• Andre Osterloh:
  Deterministic Hot-Potato Permutation Routing on the Mesh and the Torus. 223-233
  
• Bin Fu, Ming-Yang Kao, Lusheng Wang:
  Efficient Algorithms for Model-Based Motif Discovery from Multiple Sequences. 234-245
  
• Pok-Son Kim, Arne Kutzner:
  Ratio Based Stable In-Place Merging. 246-257
  
• Mathias Barra:
  A Characterisation of the Relations Definable in Presburger Arithmetic. 258-269
  
• Mingyu Xiao:
  Finding Minimum 3-Way Cuts in Hypergraphs. 270-281
  
• Jinsong Tan:
  Inapproximability of Maximum Weighted Edge Biclique and Its Applications. 282-293
  
• Haibin Zhang, Zhenhua Duan:
  Symbolic Algorithm Analysis of Rectangular Hybrid Systems. 294-305
  
• Beate Bollig:
  On the OBDD Complexity of the Most Significant Bit of Integer Multiplication. 306-317
  
• Olaf Beyersdorff:
  Logical Closure Properties of Propositional Proof Systems. 318-329
  
• Pinar Heggernes, Daniel Meister, Charis Papadopoulos:
  Graphs of Linear Clique-Width at Most 3. 330-341
  
• Kazuyuki Amano, Jun Tarui:
  A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds. 342-350
  
• Zining Cao:
  A Logic for Distributed Higher Order pi-Calculus. 351-363
  
• Marc Demange, Tinaz Ekim:
  Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs. 364-374
  
• Grégory Lafitte, Michael Weiss:
  A Topological Study of Tilings. 375-387
  
• Thomas Anberrée:
  A Denotational Semantics for Total Correctness of Sequential Exact Real Programs. 388-399
  
• Ernst-Erich Doberkat:
  Weak Bisimulations for the Giry Monad (Extended Abstract). 400-409
  
• Cindy Y. Li, Prudence W. H. Wong, Qin Xin, Fencol C. C. Yung:
  Approximating Border Length for DNA Microarray Synthesis. 410-422
  
• Klaus Ambos-Spies, Serikzhan Badaev, Sergey Goncharov:
  On a Question of Frank Stephan. 423-432
  
• Minzhu Xie, Jianxin Wang, Jianer Chen:
  A Practical Parameterized Algorithm for the Individual Haplotyping Problem MLF. 433-444
  
• Jiong Guo, Falk Hüffner, Christian Komusiewicz, Yong Zhang:
  Improved Algorithms for Bicluster Editing. 445-456
  
• Rupert Hölzl, Wolfgang Merkle:
  Generation Complexity Versus Distinction Complexity. 457-466
  
• Stephane Durocher, Evangelos Kranakis, Danny Krizanc, Lata Narayanan:
  Balancing Traffic Load Using One-Turn Rectilinear Routing. 467-478
  
• Serge Gaspers, Saket Saurabh, Alexey A. Stepanov:
  A Moderately Exponential Time Algorithm for Full Degree Spanning Tree. 479-489
  
• Oriana Ponta, Falk Hüffner, Rolf Niedermeier:
  Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems. 490-501
  
• John Z. Zhang, Tsunehiko Kameda:
  A Linear-Time Algorithm for Finding All Door Locations That Make a Room Searchable. 502-513
  
• Bakhadyr Khoussainov, Mia Minnes:
  Model Theoretic Complexity of Automatic Structures (Extended Abstract). 514-525
  
• Rahul Jain, Ashwin Nayak, Yi Su:
  A Separation between Divergence and Holevo Information for Ensembles. 526-541
  
• Bakhadyr Khoussainov, Jiamou Liu, Mia Minnes:
  Unary Automatic Graphs: An Algorithmic Perspective. 542-553
  
• Micah Adler, Brent Heeringa:
  Search Space Reductions for Nearest-Neighbor Queries. 554-567
  
• Marat M. Arslanov, S. Barry Cooper, Iskander Sh. Kalimullin, Mariya Ivanova Soskova:
  Total Degrees and Nonsplitting Properties of Enumeration Degrees. 568-578
  
• Thomas F. Kent:
  s-Degrees within e-Degrees. 579-587
  
• S. Barry Cooper, Matthew C. Salts, Guohua Wu:
  The Non-isolating Degrees Are Upwards Dense in the Computably Enumerable Degrees. 588-596