Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-105 | 27th October 2009 12:12

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

RSS-Feed




TR09-105
Authors: Vikraman Arvind, Srikanth Srinivasan
Publication: 27th October 2009 13:46
Downloads: 3457
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint