Treffer: The Remote Point Problem, Small Bias Space, and Expanding Generator Sets
Title:
The Remote Point Problem, Small Bias Space, and Expanding Generator Sets
Authors:
Contributors:
Institute of Mathematical Sciences [Chennai] (IMSc), Inria Nancy Grand Est & Loria, Jean-Yves Marion and Thomas Schwentick
Source:
27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010. :59-70
Publisher Information:
HAL CCSD, 2010.
Publication Year:
2010
Collection:
collection:STACS2010
Subject Terms:
small bias spaces, expander graphs, cayley graphs, remote point problem, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, [INFO.INFO-CC]Computer Science [cs], Computational Complexity [cs.CC], [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS]
Subject Geographic:
Original Identifier:
HAL:
Document Type:
Konferenz
conferenceObject<br />Conference papers
Language:
English
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00455338v1
Database:
HAL
Weitere Informationen
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].