Theory and Applications of Models of Computation: 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings

Front Matter....Pages -
Designing Algorithms with Limited Work Space....Pages 1-1
A Compact Encoding of Unordered Binary Trees....Pages 106-113
Low Distortion Metric Embedding into Constant Dimension....Pages 114-123
A Better Upper Bound on Weights of Exact Threshold Functions....Pages 124-132
Submodular Function Minimization under a Submodular Set Covering Constraint....Pages 133-141
Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions....Pages 142-153
Energy and Fan-In of Threshold Circuits Computing Mod Functions....Pages 154-163
NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o (loglog n ) Depth....Pages 164-170
Group-Theoretic Lower Bounds for the Complexity of Matrix Multiplication....Pages 2-13
A Real Elementary Approach to the Master Recurrence and Generalizations....Pages 14-26
Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines....Pages 27-36
Approximating Edge Dominating Set in Dense Graphs....Pages 37-47
Near Approximation of Maximum Weight Matching through Efficient Weight Reduction....Pages 48-57
Approximability of the Subset Sum Reconfiguration Problem....Pages 58-69
An Improved Kernel for Planar Connected Dominating Set....Pages 70-81
Fast Exact Algorithm for L (2,1)-Labeling of Graphs....Pages 82-93
An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree....Pages 94-105
Quantum Complexity: Some Recent Results, Some Open Problems, Some Thoughts....Pages 171-171
Non-adaptive Complex Group Testing with Multiple Positive Sets....Pages 172-183
How to Cut a Graph into Many Pieces....Pages 184-194
A Note on Obfuscation for Cryptographic Functionalities of Secret-Operation Then Public-Encryption....Pages 377-389
Grey-Box Steganography....Pages 390-402
Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models....Pages 403-408
The Hardness of Median in the Synchronized Bit Communication Model....Pages 409-415
Closed Left-R.E. Sets....Pages 218-229
 $\it \Pi^0_1$ Sets and Tilings....Pages 230-239
Intuitive Probability Logic....Pages 240-251
An Algebraic Characterization of Strictly Piecewise Languages....Pages 252-263
On the Amount of Nonconstructivity in Learning Recursive Functions....Pages 332-343
A Bad Instance for k-Means++....Pages 344-352
Catching a Fast Robber on Interval Graphs....Pages 353-364
Some Tractable Win-Lose Games....Pages 365-376
Deterministic Algorithms for Multi-criteria TSP....Pages 264-275
Extending Partial Representations of Interval Graphs....Pages 276-285
Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way....Pages 286-297
The Complexity and Approximability of Minimum Contamination Problems....Pages 298-307
On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric....Pages 308-319
Lower Bounds for Testing Computability by Small Width OBDDs....Pages 320-331
Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet....Pages 195-205
Integer Representations towards Efficient Counting in the Bit Probe Model....Pages 206-217
Lower Bounds for the Smoothed Number of Pareto Optimal Solutions....Pages 416-427
Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands....Pages 428-439
Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects....Pages 440-451
Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem....Pages 452-462
Switching to Hedgehog-Free Graphs Is NP-Complete....Pages 463-470
Locally Injective Homomorphism to the Simple Weight Graphs....Pages 471-482
Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width....Pages 483-494
Hide-and-Seek: Algorithms for Polygon Walk Problems....Pages 495-504
Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory....Pages 505-516
On the Polynomial Depth of Various Sets of Random Strings....Pages 517-527
Edge Contractions in Subclasses of Chordal Graphs....Pages 528-539
Planarity Testing Revisited....Pages 540-551
Generalized Satisfiability for the Description Logic $\mathcal{ALC}$ ....Pages 552-562
Back Matter....Pages -