Vikraman Arvind

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

    Authors: Vikraman Arvind, Srikanth Srinivasan
    Subjects: Computational Complexity
    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$.

Syndicate content