8. TAMC 2011: Tokyo, Japan

Invited Talk 1

• Tetsuo Asano:
  Designing Algorithms with Limited Work Space. 1
  

General Algorithms

• Alexey Pospelov:
  Group-Theoretic Lower Bounds for the Complexity of Matrix Multiplication. 2-13
  
• Chee Yap:
  A Real Elementary Approach to the Master Recurrence and Generalizations. 14-26
  
• Paul C. Bell, Prudence W. H. Wong:
  Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines. 27-36
  

Approximation I

• Richard Schmied, Claus Viehmann:
  Approximating Edge Dominating Set in Dense Graphs. 37-47
  
• Andrzej Lingas, Cui Di:
  Near Approximation of Maximum Weight Matching through Efficient Weight Reduction. 48-57
  
• Takehiro Ito, Erik D. Demaine:
  Approximability of the Subset Sum Reconfiguration Problem. 58-69
  

Graph Algorithms I

• Weizhong Luo, Jianxin Wang, Qilong Feng, Jiong Guo, Jianer Chen:
  An Improved Kernel for Planar Connected Dominating Set. 70-81
  
• Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Peter Rossmanith, Pawel Rzazewski:
  Fast Exact Algorithm for L(2, 1)-Labeling of Graphs. 82-93
  
• Takehiro Ito, Kazuto Kawamura, Xiao Zhou:
  An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree. 94-105
  

Complexity I

• Kozue Iwata, Shiro Ishiwata, Shin-Ichi Nakano:
  A Compact Encoding of Unordered Binary Trees. 106-113
  
• András Faragó:
  Low Distortion Metric Embedding into Constant Dimension. 114-123
  
• Xue Chen, Guangda Hu, Xiaoming Sun:
  A Better Upper Bound on Weights of Exact Threshold Functions. 124-132
  

Optimization I

• Naoyuki Kamiyama:
  Submodular Function Minimization under a Submodular Set Covering Constraint. 133-141
  
• Akiyoshi Shioura, Shunya Suzuki:
  Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions. 142-153
  

Circuit Complexity

• Akira Suzuki, Kei Uchizawa, Xiao Zhou:
  Energy and Fan-In of Threshold Circuits Computing Mod Functions. 154-163
  
• Fengming Wang:
  NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth. 164-170
  

Invited Talk 2

• Richard J. Lipton:
  Quantum Complexity: Some Recent Results, Some Open Problems, Some Thoughts. 171
  

Data Structures

• Francis Y. L. Chin, Henry C. M. Leung, Siu-Ming Yiu:
  Non-adaptive Complex Group Testing with Multiple Positive Sets. 172-183
  
• Ruben van der Zwaan, André Berger, Alexander Grigoriev:
  How to Cut a Graph into Many Pieces. 184-194
  
• Pooya Davoodi, S. Srinivasa Rao:
  Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet. 195-205
  
• Gerth Stølting Brodal, Mark Greve, Vineet Pandey, Srinivasa Rao Satti:
  Integer Representations towards Efficient Counting in the Bit Probe Model. 206-217
  

Logic and Formal Language Theory

• Sanjay Jain, Frank Stephan, Jason Teutsch:
  Closed Left-R.E. Sets. 218-229
  
• Emmanuel Jeandel, Pascal Vanier:
  P⁰₁\it \Pi^0_1 Sets and Tilings. 230-239
  
• Chunlai Zhou:
  Intuitive Probability Logic. 240-251
  
• Jie Fu, Jeffrey Heinz, Herbert G. Tanner:
  An Algebraic Characterization of Strictly Piecewise Languages. 252-263
  

Graph Algorithms II

• Bodo Manthey:
  Deterministic Algorithms for Multi-criteria TSP. 264-275
  
• Pavel Klavík, Jan Kratochvíl, Tomás Vyskocil:
  Extending Partial Representations of Interval Graphs. 276-285
  
• Serafino Cicerone:
  Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way - (Extended Abstract). 286-297
  

Approximation II

• Angsheng Li, Linqing Tang:
  The Complexity and Approximability of Minimum Contamination Problems. 298-307
  
• Ernst Althaus, Joschka Kupilas, Rouven Naujoks:
  On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric. 308-319
  
• Joshua Brody, Kevin Matulef, Chenggang Wu:
  Lower Bounds for Testing Computability by Small Width OBDDs. 320-331
  

Games and Learning Theory

• Rusins Freivalds, Thomas Zeugmann:
  On the Amount of Nonconstructivity in Learning Recursive Functions. 332-343
  
• Tobias Brunsch, Heiko Röglin:
  A Bad Instance for k-Means++. 344-352
  
• Tomás Gavenciak:
  Catching a Fast Robber on Interval Graphs. 353-364
  
• Samir Datta, Nagarajan Krishnamurthy:
  Some Tractable Win-Lose Games. 365-376
  

Cryptography and Communication Complexity

• Ning Ding, Dawu Gu:
  A Note on Obfuscation for Cryptographic Functionalities of Secret-Operation Then Public-Encryption. 377-389
  
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Grey-Box Steganography. 390-402
  
• Ming Lam Leung, Yang Li, Shengyu Zhang:
  Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models. 403-408
  
• Karolina Soltys:
  The Hardness of Median in the Synchronized Bit Communication Model. 409-415
  

Optimization II

• Tobias Brunsch, Heiko Röglin:
  Lower Bounds for the Smoothed Number of Pareto Optimal Solutions. 416-427
  
• Takuro Fukunaga:
  Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands. 428-439
  
• Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa:
  Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects. 440-451
  

Complexity II

• Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno:
  Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem. 452-462
  
• Eva Jelínková:
  Switching to Hedgehog-Free Graphs Is NP-Complete. 463-470
  
• Ondrej Bílka, Bernard Lidický, Marek Tesar:
  Locally Injective Homomorphism to the Simple Weight Graphs. 471-482
  

Graph Algorithms III

• Benjamin Hellouin de Menibus, Takeaki Uno:
  Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width. 483-494
  
• Atlas F. Cook, Chenglin Fan, Jun Luo:
  Hide-and-Seek: Algorithms for Polygon Walk Problems. 495-504
  
• Alexander Langer, Peter Rossmanith, Somnath Sikdar:
  Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory - (Extended Abstract). 505-516
  

Complexity III

• Philippe Moser:
  On the Polynomial Depth of Various Sets of Random Strings. 517-527
  
• Rémy Belmonte, Pinar Heggernes, Pim van 't Hof:
  Edge Contractions in Subclasses of Chordal Graphs. 528-539
  
• Samir Datta, Gautam Prakriya:
  Planarity Testing Revisited. 540-551
  
• Arne Meier, Thomas Schneider:
  Generalized Satisfiability for the Description Logic ALC\mathcal{ALC} - (Extended Abstract). 552-562
  

Last update Fri May 25 08:42:51 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page