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

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].
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.59-70, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455338
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 10:30:26
Dernière modification le : mercredi 10 février 2010 - 11:21:36
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:52:03

Fichier

Arvind.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455338, version 1

Collections

Citation

Vikraman Arvind, Srikanth Srinivasan. The Remote Point Problem, Small Bias Space, and Expanding Generator Sets. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.59-70, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455338〉

Partager

Métriques

Consultations de la notice

116

Téléchargements de fichiers

49