Fourier Growth of Regular Branching Programs
Fourier Growth of Regular Branching Programs
复制标题
正则分支程序的傅立叶增长
DOI：
10.4230/lipics.approx/random.2022.2
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
S. Vadhan
中科院分区：
文献类型：
--
作者：
Chin Ho Lee;Edward Pyne;S. Vadhan
本文分析了只读正则分支程序的Fourier增长，即在k层（记为L1，k）上的L1 Fourier权.本文证明了每个宽度为w ∈ [1，∞ ]的只读正则分支程序B在n位输入上具有s个接受状态时，其L1，k必有min n Pr [ B（un）= 1]（w − 1）k，s · O（cid：0）（nlog n）/k（cid：1）k − 12 o的界.对于任何常数k，我们的结果对于w-1位的AND函数是紧到常数因子的，并且对于无限宽度的程序是紧到多对数因子的。特别地，对于k = 1，我们有L 1，1（B）≤ s，与程序的宽度w无关。我们的结果给出了硬币问题的新的边界和新的伪随机生成器（PRG）。此外，我们还获得了具有常数因子延伸的无界宽度的无序置换分支程序的显式生成器，其中以前没有已知的PRG。应用Bhusasiok，Ivanov，Jin，Lee，Servedio和Viola（RANDOM 2021）的复合定理，我们将结果扩展到“广义群积”，即模和和乘积检验的推广。
We analyze the Fourier growth , i.e. the L 1 Fourier weight at level k (denoted L 1 ,k ), of read-once regular branching programs. We prove that every read-once regular branching program B of width w ∈ [1 , ∞ ] with s accepting states on n -bit inputs must have its L 1 ,k bounded by min n Pr [ B ( U n ) = 1]( w − 1) k , s · O (cid:0) ( n log n ) /k (cid:1) k − 12 o . For any constant k , our result is tight up to constant factors for the AND function on w − 1 bits, and is tight up to polylogarithmic factors for unbounded width programs. In particular, for k = 1 we have L 1 , 1 ( B ) ≤ s , with no dependence on the width w of the program. Our result gives new bounds on the coin problem and new pseudorandom generators (PRGs). Furthermore, we obtain an explicit generator for unordered permutation branching programs of unbounded width with a constant factor stretch, where no PRG was previously known. Applying a composition theorem of Błasiok, Ivanov, Jin, Lee, Servedio and Viola (RANDOM 2021), we extend our results to “generalized group products,” a generalization of modular sums and product tests.
登录
查看更多内容
用于以任意顺序读取一次的分支程序的伪随机生成器
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
第二傅立叶级伪随机发生器及其在具有奇偶校验门的 AC0 中的应用
DOI：
--
发表时间：
2019
期刊：
(ITCS
影响因子：
--
作者：
Chattopadhyay, Eshan;Hatami, Pooya;Lovett, Shachar;Tal, Avishay
通讯作者：
Tal, Avishay
数据流应用程序的硬币问题
DOI：
10.1109/focs46700.2020.00038
发表时间：
2020
期刊：
61st {IEEE} Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Braverman, Mark;Garg, Sumegha;Woodruff, David P.
通讯作者：
Woodruff, David P.
关系式异或的下界
DOI：
10.4230/lipics.approx/random.2021.52
发表时间：
2021
影响因子：
--
作者：
Girish, Uma;Raz, Ran;Zhan, Wei
通讯作者：
Zhan, Wei
AC0[p] 通过硬币问题针对 MCSP 的下界
DOI：
--
发表时间：
2019
期刊：
ICALP
影响因子：
--
作者：
Golovnev, Alexander;Ilango, Rahul;Impagliazzo, Russell;Kabanets, Valentine;Kolokolova, Antonina;Tal, Avishay
通讯作者：
Tal, Avishay