The Remote Point Problem, Small Bias Space, and Expanding Generator Sets - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2010

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].
Fichier principal
Vignette du fichier
Arvind.pdf (215.22 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00455338 , version 1 (10-02-2010)

Identifiers

  • HAL Id : inria-00455338 , version 1

Cite

Vikraman Arvind, Srikanth Srinivasan. The Remote Point Problem, Small Bias Space, and Expanding Generator Sets. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.59-70. ⟨inria-00455338⟩

Collections

STACS2010
69 View
56 Download

Share

Gmail Facebook X LinkedIn More