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
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
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-complete;...
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
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′...