Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 2 Issue 2, March 2011

Lower Bounds for Coin-Weighing Problems
Eric Purdy
Article No.: 3
DOI: 10.1145/1944857.1944858

Among a set of n coins of two weights (good and bad), and using a balance, we wish to determine the number of bad coins using as few measurements as possible. There is a known adaptive decision tree that answers this question in...

Solvable Group Isomorphism Is (Almost) in NP ∩ coNP
Vikraman Arvind, Jacobo Torán
Article No.: 4
DOI: 10.1145/1944857.1944859

The Group Isomorphism problem consists in deciding whether two input groups G1 and G2 given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group...

A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier
Article No.: 5
DOI: 10.1145/1944857.1944860

We investigate the computational complexity of a general “compression task” centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization problems. The core issue...