首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Deterministic Approximation of Random Walks in Small Space
  • 本地全文:下载
  • 作者:Jack Murtagh ; Omer Reingold ; Aaron Sidford
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2021
  • 卷号:17
  • 期号:1
  • 页码:1-35
  • DOI:10.4086/toc.2021.v017a004
  • 语种:English
  • 出版社:University of Chicago
  • 摘要:We give a deterministic, nearly logarithmic-space algorithm that given an undirected multigraph G, a positive integer r, and a set S of vertices, approximates the conductance of S in the r-step random walk on G to within a factor of 1+ϵ, where ϵ>0 is an arbitrarily small constant. More generally, our algorithm computes an ϵ-spectral approximation to the normalized Laplacian of the r-step walk.Our algorithm combines the derandomized square graph operation (Rozenman and Vadhan, RANDOM'05), which we recently used for solving Laplacian systems in nearly logarithmic space (Murtagh et al., FOCS'17), with ideas from (Cheng et al., 2015) which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even r (while ours works for all r). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd r. Second, we define and analyze a generalization of the derandomized square for irregular multigraphs and for sparsifying the product of two distinct multigraphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.
  • 关键词:random walks; space complexity; derandomization; expander graphs; spectral approximation
国家哲学社会科学文献中心版权所有