The Remote Point Problem, Small Bias Space, and Expanding Generator SetsReportar como inadecuado




The Remote Point Problem, Small Bias Space, and Expanding Generator Sets - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 IMSc - Institute of Mathematical Sciences India

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.

Keywords : small bias spaces expander graphs cayley graphs remote point problem





Autor: Vikraman Arvind - Srikanth Srinivasan -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados