首页    期刊浏览 2024年07月16日 星期二
登录注册

文章基本信息

  • 标题:The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets
  • 本地全文:下载
  • 作者:Vikraman Arvind ; Srikanth Srinivasan
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Using -bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an NC2 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 NC2 algorithm for RPP, again using -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].

  • 关键词:Expander Graphs; Remote point problem; Small bias spaces
国家哲学社会科学文献中心版权所有