ICS 2011

Welcome to ICS2011
Innovations in Computer Science  ICS 2011, Tsinghua University, Beijing, China, January 79, 2011. Proceedings, 496508, 9787302245179
Tsinghua University Press
We study extensions of the kSUM 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 wellstudied 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 linearinvariant properties. We give nearly optimal bounds for TargetSum and (k, r)LinDependenceq for every r, k, and constant q. Namely, assuming 3SAT 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:

Copyright 20102011, Institute for Computer Science, Tsinghua University, All Rights Reserved.