Theory and Applications of Models of Computation

1. Front Matter

   PDF

2. Invited Talk 1

   1. Designing Algorithms with Limited Work Space

      • Tetsuo Asano

      Pages 1-1

   2. Session 1A: General Algorithms

      1. Group-Theoretic Lower Bounds for the Complexity of Matrix Multiplication

         • Alexey Pospelov

         Pages 2-13

      2. A Real Elementary Approach to the Master Recurrence and Generalizations

         • Chee Yap

         Pages 14-26

      3. Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines

         • Paul C. Bell, Prudence W. H. Wong

         Pages 27-36

   3. Session 1B: Approximation I

      1. Approximating Edge Dominating Set in Dense Graphs

         • Richard Schmied, Claus Viehmann

         Pages 37-47

      2. Near Approximation of Maximum Weight Matching through Efficient Weight Reduction

         • Andrzej Lingas, Cui Di

         Pages 48-57

      3. Approximability of the Subset Sum Reconfiguration Problem

         • Takehiro Ito, Erik D. Demaine

         Pages 58-69

   4. Session 2A: Graph Algorithms I

      1. An Improved Kernel for Planar Connected Dominating Set

         • Weizhong Luo, Jianxin Wang, Qilong Feng, Jiong Guo, Jianer Chen

         Pages 70-81

      2. Fast Exact Algorithm for <i>L</i>(2,1)-Labeling of Graphs

         • Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Peter Rossmanith, Paweł Rza̧żewski

         Pages 82-93

      3. An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree

         • Takehiro Ito, Kazuto Kawamura, Xiao Zhou

         Pages 94-105

   5. Session 2B: Complexity I

      1. A Compact Encoding of Unordered Binary Trees

         • Kozue Iwata, Shiro Ishiwata, Shin-ichi Nakano

         Pages 106-113

      2. Low Distortion Metric Embedding into Constant Dimension

         • András Faragó

         Pages 114-123

      3. A Better Upper Bound on Weights of Exact Threshold Functions

         • Xue Chen, Guangda Hu, Xiaoming Sun

         Pages 124-132

   6. Session 3A: Optimization I

      1. Submodular Function Minimization under a Submodular Set Covering Constraint

         • Naoyuki Kamiyama

         Pages 133-141

      2. Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions

         • Akiyoshi Shioura, Shunya Suzuki

         Pages 142-153

   7. Session 3B: Circuit Complexity

      1. Energy and Fan-In of Threshold Circuits Computing Mod Functions

         • Akira Suzuki, Kei Uchizawa, Xiao Zhou

         Pages 154-163

      2. NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of <i>o</i>(loglog<i>n</i>) Depth

         • Fengming Wang

         Pages 164-170

3. Invited Talk 2

   1. Quantum Complexity: Some Recent Results, Some Open Problems, Some Thoughts

      • Richard J. Lipton

      Pages 171-171

   2. Session 4A: Data Structures

      1. Non-adaptive Complex Group Testing with Multiple Positive Sets

         • Francis Y. L. Chin, Henry C. M. Leung, S. M. Yiu

         Pages 172-183

This book constitutes the refereed proceedings of the 8th International Conference on Theory and Applications of Models of Computation, TAMC 2011, held in Tokyo, Japan, in May 2011. The 51 revised full papers presented together with the abstracts of 2 invited talks were carefully reviewed and selected from 136 submissions. The papers address the three main themes of the conference which were computability, complexity, and algorithms and are organized in topical sections on general algorithms, approximation, graph algorithms, complexity, optimization, circuit complexity, data structures, logic and formal language theory, games and learning theory, and cryptography and communication complexity.

• computational geometry
• energy complexity
• modal logic
• ontology
• probability logic
• algorithm analysis and problem complexity

• Department of Computer Science, University of Miami, Coral Gables, USA

  Mitsunori Ogihara

• Department of Information and Communication Engineering, University of Electro-Comm, Tokyo, Japan

  Jun Tarui

Policies and ethics