Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR09-105 | 27th October 2009 12:12

#### The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

TR09-105
Authors: Vikraman Arvind, Srikanth Srinivasan
Publication: 27th October 2009 13:46
Using $\epsilon$-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed group G. When G is Abelian, we give an $NC^2$ algorithm for RPP, again using $\epsilon$-bias spaces. For nonabelian G, we give a deterministic polynomial-time algorithm for RPP. We also show the connection to construction of expanding generator sets for the group G^n . All our algorithms for the RPP achieve essentially the same parameters as [APY09].