On the Power of Regular and Permutation Branching Programs
On the Power of Regular and Permutation Branching Programs
复制标题
论正则分支程序和排列分支程序的威力
DOI：
10.4230/lipics.approx/random.2023.44
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Salil P. Vadhan
中科院分区：
文献类型：
--
作者：
Chin Ho Lee;Edward Pyne;Salil P. Vadhan
我们给出了几类受限制的任意阶一次读取分支程序(ROBP)和标准阶ROBP(SOBP)的功率的新的上下界，这些程序在空间有界计算的伪随机性的文献中受到了很大的关注。长度为n、宽度为⌊w(n+1)/2⌋的正则SOBP可以精确地模拟长度为n、宽度为w的一般SOBP，并且宽度为n/2的−o(N)爆破是此类模拟所必需的。我们的结果扩展和简化了先前的平均情况模拟(Reingold，Trevisan和Vadhan(STEC 2006)，Bogdanov，Hoza，Prakya和Pyne(CCC 2022))，特别是意味着对于宽度为Poly(N)或更大的规则SOBP，加权伪随机生成器(Braverman，Cohen和Garg(SICOMP 2020))自动扩展到一般SOBP。此外，我们的模拟还扩展到一般的(甚至是多次阅读的)忽略分支程序。对于指数宽度的置换SOBP，存在着一般情况下难以用等宽度的正则SOBP计算的自然函数。事实上，我们证明了对于指数宽度的任意阶置换ROBP，内积mod 2是平均情形困难的。对于指数宽度的SOBP，存在着最坏情况下难以计算的等宽任意阶置换ROBP函数。次指数宽度的两次读置换分支程序可以模拟多项式宽度的任意阶ROBPs。
We give new upper and lower bounds on the power of several restricted classes of arbitrary-order read-once branching programs (ROBPs) and standard-order ROBPs (SOBPs) that have received significant attention in the literature on pseudorandomness for space-bounded computation. Regular SOBPs of length n and width ⌊ w ( n +1) / 2 ⌋ can exactly simulate general SOBPs of length n and width w , and moreover an n/ 2 − o ( n ) blow-up in width is necessary for such a simulation. Our result extends and simplifies prior average-case simulations (Reingold, Trevisan, and Vadhan (STOC 2006), Bogdanov, Hoza, Prakriya, and Pyne (CCC 2022)), in particular implying that weighted pseudorandom generators (Braverman, Cohen, and Garg (SICOMP 2020)) for regular SOBPs of width poly( n ) or larger automatically extend to general SOBPs. Furthermore, our simulation also extends to general (even read-many) oblivious branching programs. There exist natural functions computable by regular SOBPs of constant width that are average-case hard for permutation SOBPs of exponential width. Indeed, we show that Inner-Product mod 2 is average-case hard for arbitrary-order permutation ROBPs of exponential width. There exist functions computable by constant-width arbitrary-order permutation ROBPs that are worst-case hard for exponential-width SOBPs. Read-twice permutation branching programs of subexponential width can simulate polynomial-width arbitrary-order ROBPs.
登录
查看更多内容
用于以任意顺序读取一次的分支程序的伪随机生成器
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
用于无限宽度/自适应顺序只读分支程序的新 PRG
DOI：
10.4230/lipics.icalp.2023.39
发表时间：
2023
期刊：
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
影响因子：
--
作者：
Chen, Lijie;Lyu, Xin;Tal, Avishay;Wu, Hongxun
通讯作者：
Wu, Hongxun
用于只读单调分支程序的伪随机生成器
DOI：
10.4230/lipics.approx/random.2021.58
发表时间：
2021
影响因子：
--
作者：
Doron, Dean;Meka, Raghu;Reingold, Omer;Tal, Avishay;Vadhan, Salil
通讯作者：
Vadhan, Salil
通过流式 XOR 引理进行参数估计和属性测试的图流式下界
DOI：
10.1145/3406325.3451110
发表时间：
2021
期刊：
2021
影响因子：
--
作者：
Assadi, Sepehr;N, Vishvajeet
通讯作者：
N, Vishvajeet