The Remote Point Problem, Small Bias Space, and Expanding Generator Sets

الأصل · EN

Using ε-bias spaces over F₂, we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an NC² algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace Fⁿ by Gⁿ for an arbitrary fixed group G. When G is Abelian, we give an NC² algorithm for RPP, again using ε-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ⁿ. All our algorithms for the RPP achieve essentially the same parameters as [APY09].