2026-07-23T00:26:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2444 2024-03-06T10:33:21Z ddc:004 open_access

The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets Arvind, Vikraman Srinivasan, Srikanth Small Bias Spaces Expander Graphs Cayley Graphs Remote Point Problem Using $\varepsilon$-bias spaces over $\F_2$, we show that the Remote Point Problem (RPP), introduced by Alon et al \cite{APY09}, has an $\NC^2$ algorithm (achieving the same parameters as \cite{APY09}). We study a generalization of the Remote Point Problem to groups: we replace $\F_2^n$ by $\mcG^n$ for an arbitrary fixed group $\mcG$. When $\mcG$ is Abelian we give an $\NC^2$ algorithm for RPP, again using $\varepsilon$-bias spaces. For nonabelian $\mcG$, we give a deterministic polynomial-time algorithm for RPP. We also show the connection to construction of expanding generator sets for the group $\mcG^n$. All our algorithms for the RPP achieve essentially the same parameters as \cite{APY09}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vikraman Arvind and Srikanth Srinivasan 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2444 urn:nbn:de:0030-drops-24449 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2444 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode