Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size
Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size
复制标题
通过无限大小图中的查询实现随机游走的确定性逼近
DOI：
10.1137/1.9781611977066.5
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Vadhan, Salil
中科院分区：
文献类型：
--
作者：
Pyne, Edward;Vadhan, Salil
考虑下面的计算问题：给定一个正则有向图G =（V，E），两个顶点u，v <$V，和一个游动长度t <$N，估计一个长度t从v到t的随机游动在±ε内结束的概率。一个随机算法可以解决这个问题，执行O（1/ε2）的长度从m的随机行走，并输出结束atv的分数。本文中，我们研究了这个问题的确定性算法，也限于执行长度从m的行走，并看到哪些结束atv。具体地说，如果Gisd-正则，算法被给予对函数f：[d]t→ {0，1}的oracle访问，其中f（x）是1，如果由边标签指定的行走从x到atv。我们假设thatG是一致的标签，这意味着标签的边缘，为eachi [d]形成一个置换V。我们表明，存在一个确定性的算法，使聚（dt/ε）非自适应查询tof，无论在图G的顶点数。至关重要的是，与随机算法相比，我们的算法并不简单地输出其查询的平均值。事实上，Hoza，Pyne和Vadhan（ITCS 2021）表明，任何后一种形式的确定性算法，适用于无限大小的图必须至少具有查询复杂度。在伪随机性的语言中，我们的结果是“确定性采样器”和“确定性平均采样器”的查询复杂度之间的分离“无限宽度的置换分支程序”。我们的分离比Pyne和Vadhan（CCC 2021）的分离更强，并且具有更简单的证明（不使用谱图理论或Impagliazzo-Nisan-Wigderson伪随机生成器）。另一方面，Pyne和Vadhan的算法是显式的，在小空间中是可计算的，而我们的算法不是显式的（除非我们假设存在一个最优的显式伪随机生成器用于有界宽度的置换分支程序）。
Consider the following computational problem: given a regular digraphG= (V,E), two verticesu,v∊V, and a walk lengtht∊N, estimate the probability that a random walk of lengthtfromuends atvto within ±ε. A randomized algorithm can solve this problem by carrying outO(1/ε2) random walks of lengthtfromuand outputting the fraction that end atv.In this paper, we studydeterministicalgorithms for this problem that are also restricted to carrying out walks of lengthtfromuand seeing which ones end atv. Specifically, ifGisd-regular, the algorithm is given oracle access to a functionf: [d]t→ {0,1} wheref(x) is 1 if the walk fromuspecified by the edge labels inxends atv. We assume thatGisconsistently labelled, meaning that the edges of labelifor eachi∊ [d] form a permutation onV.We show that there exists a deterministic algorithm that makes poly(dt/ε) nonadaptive queries tof, regardless of the number of vertices in the graphG. Crucially, and in contrast to the randomized algorithm, our algorithm does not simply output the average value of its queries. Indeed, Hoza, Pyne, and Vadhan (ITCS 2021) showed that any deterministic algorithm of the latter form that works for graphs of unbounded size must have query complexity at least .In the language of pseudorandomness, our result is a separation between the query complexity of “deterministic samplers” and “deterministic averaging samplers” for the class of “permutation branching programs of unbounded width”. Our separation is stronger than the prior separation of Pyne and Vadhan (CCC 2021), and has a much simpler proof (not using spectral graph theory or the Impagliazzo-Nisan-Wigderson pseudorandom generator). On the other hand, the algorithm of Pyne and Vadhan is explicit and computable in small space, whereas ours is not explicit (unless we assume the existence of an optimal explicit pseudorandom generator for permutation branching programs of bounded width).
登录
查看更多内容
用于宽度 3 分支程序的伪随机生成器
DOI：
10.1145/3313276.3316319
发表时间：
2018
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Raghu Meka;Omer Reingold;Avishay Tal
通讯作者：
Avishay Tal
更好的空间有限计算的伪分布和去随机化
影响因子：
4.1
作者：
William M. Hoza
通讯作者：
William M. Hoza
小空间随机游走的高精度估计
DOI：
10.1109/focs46700.2020.00123
发表时间：
2020
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Ahmadinejad, AmirMahdi;Kelner, Jonathan;Murtagh, Jack;Peebles, John;Sidford, Aaron;Vadhan, Salil
通讯作者：
Vadhan, Salil
对于一次读取分支程序，命中集具有接近最优的错误
DOI：
10.1145/3188745.3188780
发表时间：
2018
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
M. Braverman;Gil Cohen;Sumegha Garg
通讯作者：
Sumegha Garg
图的去随机平方
DOI：
10.1007/11538462_37
发表时间：
2005
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Eyal Rozenman;S. Vadhan
通讯作者：
S. Vadhan