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

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

2009-09-29

arxiv.org/abs/0909.5313v3

Computer Science

Computational Complexity

accepted to STACS 2010, conference version, 16 pages

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

The Remote Point Problem, Small Bias Space, and Expanding Generator Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Remote Point Problem, Small Bias Space, and Expanding Generator Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Remote Point Problem, Small Bias Space, and Expanding Generator Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664745