TR09-105 Authors: Vikraman Arvind, Srikanth Srinivasan

Publication: 27th October 2009 13:46

Downloads: 2266

Keywords:

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].