Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 7 Issue 3, July 2015

Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems
Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis
Article No.: 10
DOI: 10.1145/2698587

Alice and Bob want to know if two strings of length n are almost equal. That is, do the strings differ on at most a bits? Let 0 ⩽ an − 1. We show (1) any deterministic protocol—as well as...

Some Hard Families of Parameterized Counting Problems
Mark Jerrum, Kitty Meeks
Article No.: 11
DOI: 10.1145/2786017

We consider parameterized subgraph counting problems of the following form: given a graph G, how many k-tuples of its vertices induce a subgraph with a given property? A number of such problems are known to be #W[1]-complete;...

Mutual Dimension
Adam Case, Jack H. Lutz
Article No.: 12
DOI: 10.1145/2786566

We define the lower and upper mutual dimensions mdim(x: y) and Mdim(x: y) between any two points x and y in Euclidean space. Intuitively, these are the lower and upper...

Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps
Henning Fernau, Alejandro López-Ortiz, Jazmín Romero
Article No.: 13
DOI: 10.1145/2786015

We consider the problem of discovering overlapping communities in networks that we model as generalizations of the Set and Graph Packing problems with overlap. As usual for Set Packing problems, we seek a collection S...