Theory and Applications of Models of Computation: 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings

Front Matter....Pages I-XII
Front Matter....Pages 1-1
Hilbert’s Tenth Problem for Subrings of $${\mathbb {Q}}$$ and Number Fields (Extended Abstract)....Pages 3-9
Nondeterministic Separations....Pages 10-17
Quantum and Randomized Query Complexities (Extended Abstract)....Pages 18-19
Front Matter....Pages 21-21
Algorithmically Random Functions and Effective Capacities....Pages 23-37
Where Join Preservation Fails in the Bounded Turing Degrees of C.E. Sets....Pages 38-49
Structured Frequency Algorithms....Pages 50-61
Asymptotic Properties of Combinatory Logic....Pages 62-72
Front Matter....Pages 73-73
Some New Consequences of the Hypothesis That P Has Fixed Polynomial-Size Circuits....Pages 75-86
Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems....Pages 87-98
On the Power of Parity Queries in Boolean Decision Trees....Pages 99-109
Card-Based Protocols for Any Boolean Function....Pages 110-121
Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma....Pages 122-133
Front Matter....Pages 135-135
Star Shaped Orthogonal Drawing....Pages 137-149
The Domination Number of On-line Social Networks and Random Geometric Graphs....Pages 150-163
A Linear Time Algorithm for Determining Almost Bipartite Graphs....Pages 164-176
The First-Order Contiguity of Sparse Random Graphs with Prescribed Degrees....Pages 177-188
Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls....Pages 189-199
Multi-player Diffusion Games on Graph Classes....Pages 200-211
Reconfiguration of Cliques in a Graph....Pages 212-223
The Complexity of Finding Effectors....Pages 224-235
Front Matter....Pages 135-135
Common Developments of Three Incongruent Boxes of Area 30....Pages 236-247
Finding Connected Dense $$k$$ -Subgraphs....Pages 248-259
The Complexity of Degree Anonymization by Graph Contractions....Pages 260-271
An Improved Exact Algorithm for Maximum Induced Matching....Pages 272-283
Completion of the Mixed Unit Interval Graphs Hierarchy....Pages 284-296
Bounded Treewidth and Space-Efficient Linear Algebra....Pages 297-308
Front Matter....Pages 309-309
Quantum Game Players Can Have Advantage Without Discord....Pages 311-323
Quantum Circuits for the Unitary Permutation Problem....Pages 324-331
Front Matter....Pages 333-333
Algorithms in the Ultra-Wide Word Model....Pages 335-346
Uniformity of Point Samples in Metric Spaces Using Gap Ratio....Pages 347-358
On Pure Nash Equilibria in Stochastic Games....Pages 359-371
Front Matter....Pages 373-373
Learning from Non-iid Data: Fast Rates for the One-vs-All Multiclass Plug-in Classifiers....Pages 375-387
Deletion Operations on Deterministic Families of Automata....Pages 388-399
ExplicitPRISMSymm: Symmetry Reduction Technique for Explicit Models in PRISM....Pages 400-412
Front Matter....Pages 413-413
Kernelization Algorithms for Packing Problems Allowing Overlaps....Pages 415-427
Parameterized Complexity of Asynchronous Border Minimization....Pages 428-440
Parametrized Complexity of Length-Bounded Cuts and Multi-cuts....Pages 441-452
Algorithms and Hardness for Signed Domination....Pages 453-464
Back Matter....Pages 465-466