Hitting sets for regular branching programs
Hitting sets for regular branching programs
复制标题
常规分支程序的命中集
DOI：
10.4230/lipics.ccc.2022.3
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Edward Pyne
中科院分区：
文献类型：
--
作者：
Andrej Bogdanov;William M. Hoza;Gautam Prakriya;Edward Pyne
我们构造了改进的命中集生成器（HSGs）的有序（只读一次）定期分支计划在两个参数制度。首先，我们构造了一个显式的ε-HSG，用于具有种子长度的单个接受状态的无界宽度正则分支程序[EQUATION]，其中n是程序的长度。其次，我们构造了一个显式的ε-HSG，用于种子长度为w-n的正则分支程序[方程]对于上下文，该领域的“基线”是Nisan（Combinatorica 1992）的伪随机生成器（PRG），它欺骗了种子长度为O（log（wn/ε）· log n）的有序（可能是非正则）分支程序。对于常规程序，Braverman，Rao，Raz和Yehudayoff（FOCS 2010，SICOMP 2014）提出的最先进的PRG的种子长度为log（w/ε）· log n，当log（w/ε）= o（log n）时，它超过了Nisan的种子长度。总的来说，我们的两个新构造在所有参数区域中击败了Nisan的种子长度，除了当log w和log（1/ε）都是Ω（log n）时（对于具有单个接受顶点的正则分支程序的HSG的构造）。扩展Reingold，Trevisan和Vadhan（STOC 2006）的工作，我们进一步证明了在log w = Θ（log（1/ε））= θ（log n）的机制中，具有单个接受顶点且种子长度为o（log 2 n）的正则分支程序的显式HSG将意味着一般有序分支程序的改进HSG，这将是去随机化的重大突破。Pyne和Vadhan（CCC 2021）最近获得了置换分支程序特殊情况下的此类参数。
We construct improved hitting set generators (HSGs) for ordered (read-once) regular branching programs in two parameter regimes. First, we construct an explicit ε-HSG for unbounded-width regular branching programs with a single accept state with seed length [EQUATION] where n is the length of the program. Second, we construct an explicit ε-HSG for width-w length-n regular branching programs with seed length [EQUATION] For context, the "baseline" in this area is the pseudorandom generator (PRG) by Nisan (Combinatorica 1992), which fools ordered (possibly non-regular) branching programs with seed length O(log(wn/ε) · log n). For regular programs, the state-of-the-art PRG, by Braverman, Rao, Raz, and Yehudayoff (FOCS 2010, SICOMP 2014), has seed length Õ(log(w/ε) · log n), which beats Nisan's seed length when log(w/ε) = o(log n). Taken together, our two new constructions beat Nisan's seed length in all parameter regimes except when log w and log (1/ε) are both Ω(log n) (for the construction of HSGs for regular branching programs with a single accept vertex). Extending work by Reingold, Trevisan, and Vadhan (STOC 2006), we furthermore show that an explicit HSG for regular branching programs with a single accept vertex with seed length o(log2 n) in the regime log w = Θ(log(1/ε)) = Θ(log n) would imply improved HSGs for general ordered branching programs, which would be a major breakthrough in derandomization. Pyne and Vadhan (CCC 2021) recently obtained such parameters for the special case of permutation branching programs.
登录
查看更多内容
用于以任意顺序读取一次的分支程序的伪随机生成器
DOI：
10.1109/focs.2018.00093
发表时间：
2018
期刊：
59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018
影响因子：
--
作者：
Forbes, Michael A.;Kelley, Zander
通讯作者：
Kelley, Zander
小空间随机游走的高精度估计
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
小成功 RL 的简单最佳击球组合
影响因子：
1.6
作者：
Hoza, William M.;Zuckerman, David
通讯作者：
Zuckerman, David
通过无限大小图中的查询实现随机游走的确定性逼近
DOI：
10.1137/1.9781611977066.5
发表时间：
2022
期刊：
Proceedings of the SIAM Symposium on Simplicity in Algorithms
影响因子：
--
作者：
Pyne, Edward;Vadhan, Salil
通讯作者：
Vadhan, Salil