ICS 2011

Welcome to ICS2011

Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 496-508, 978-7-302-24517-9
Tsinghua University Press

The Complexity of Linear Dependence Problems in Vector Spaces Authors : Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie [Download PDF]

Abstract:
We study extensions of the k-SUM problem to vector spaces over finite fields. Given a subset S Fnq of size r ≤ qn, an integer k, 2 ≤ k ≤ n, and a vector v ∈ (Fkq\{0})k, we define the TargetSum problem to be the problem of finding k elements xi1,..., xik ∈ S for which ∑kj=1 vjxij = z, where z may either be an input or a fixed vector. We also study a variant of this, where instead of finding xi1,..., xik ∈ S for which ∑kj=1 vjxij = z, we require that z be in span(xi1,..., xik ), which we call the (k, r)-LinDependenceq problem.
These problems are natural generalizations of well-studied problems that occur in coding theory and property testing. Indeed, the (k, r)-LinDependenceq problem is just the Maximum Likelihood Decoding problem for linear codes. Also, in the TargetSum problem, if instead of general z we require z = 0n, then this is the Weight Distribution problem for linear codes. In property testing, these problems have been implicitly studied in the context of testing linear-invariant properties.
We give nearly optimal bounds for TargetSum and (k, r)-LinDependenceq for every r, k, and constant q. Namely, assuming 3-SAT requires exponential time, we show that any algorithm for these problems must run in min(2Ɵ(n), rƟ(k)) time. Moreover, we give deterministic upper bounds that match this complexity, up to constant factors in the exponent. Our lower bound strengthens and simplifies an earlier min(2Ɵ(n), r ) lower bound for both the Maximum Likelihood Decoding and Weight Distribution problems.
We also give upper and lower bounds for variants of these problems, e.g., for the problem for which we must find xi1,..., xik for which z ∈ span(xi1,..., xik ) but z is not spanned by any proper subset of these vectors, and for the counting version of this problem.

Preview: