Search ACM DL

Search Issue

enter search term and/or author name

**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 ⩽ *a* ⩽ *n* − 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 ^{′}*...