Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
复制标题
来自新的去随机 XOR 引理的反指数相关界限和极其严格的矩阵
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Xin Lyu
中科院分区：
文献类型：
--
作者：
Lijie Chen;Xin Lyu
在这篇文章中，我们证明了存在一个函数f ∈ E NP，使得对于每个足够大的n和d = n/logn，fn（f限制为n位输入）不能用d次的F2-多项式（1/2 + 2−d）-逼近。我们还观察到一个微小的改进（例如，将d改进为n1/2+ε（对于任何ε > 0）将意味着E NP不能由2n 1/2 + ε大小的深度3 AC 0-电路计算，这是复杂性理论中众所周知的难题。使用相同的证明技巧，我们也能够在P NP中构造F2上的极刚性矩阵。更具体地说，我们证明了对于每个常数ε ∈（0，1），存在一个P NP算法，对于每个足够大的n，该算法在输入1 n上输出一个n× n的F2-矩阵Hn，满足RHn（2log 1 − ε n）≥（1/2 − exp（− log 2/3 · ε n））· n2。这改进了[Alman和Chen，FOCS 2019]和[Bhangale等人，FOCS 2020]，其仅给出Ω（n2）刚性。证明新结果的关键是一个新的基于近似线性和的去随机化XOR引理，它大致是说，给定一个n-输入函数f，它不能被F中s个函数在f1-距离内的某个线性和0.99-近似，人们可以构造一个新的函数Ampf，它的输入位数为O（n），不能被F-函数（1/2+sΩ（1））-近似。设F是一个包含低次F2-多项式或低秩F2-矩阵的函数集合，首先利用算法方法构造一个在上述意义下对F的线性和弱困难的函数，然后将去随机化的XOR引理应用于f，得到了我们的结果.我们得到了我们的新的去随机化异或引理，给出了一个推广的著名的硬核引理由Impagliazzo。我们的推广在某种意义上构造了一个弱硬函数f关于F-函数的非布尔硬核，从f的弱不可逼近性的F的任何线性和有界的非布尔范数。这个推广通过考虑范数恢复了原来的核心引理。令人惊讶的是，当我们切换到x1-范数时，我们立即重新发现了莱文对姚的XOR引理的证明。也就是说，姚的XOR引理的前两个证明可以与我们的新观点统一起来。为了证明相关性界，我们的新的去随机化XOR引理确实适用于104/3-范数。
In this work we prove that there is a function f ∈ E NP such that, for every sufficiently large n and d = √n/logn, fn (f restricted to n-bit inputs) cannot be (1/2 + 2−d)-approximated by F2-polynomials of degree d. We also observe that a minor improvement (e.g., improving d to n1/2+ε for any ε > 0) over our result would imply E NP cannot be computed by depth-3 AC0-circuits of 2n1/2 + ε size, which is a notoriously hard open question in complexity theory. Using the same proof techniques, we are also able to construct extremely rigid matrices over F2 in P NP. More specifically, we show that for every constant ε ∈ (0,1), there is a P NP algorithm which on input 1n outputs an n× n F2-matrix Hn satisfying RHn(2log1 − ε n) ≥ (1/2 − exp(−log2/3 · ε n) ) · n2, for every sufficiently large n. This improves the recent P NP constructions of rigid matrices in [Alman and Chen, FOCS 2019] and [Bhangale et al., FOCS 2020], which only give Ω(n2) rigidity. The key ingredient in the proof of our new results is a new derandomized XOR lemma based on approximate linear sums, which roughly says that given an n-input function f which cannot be 0.99-approximated by certain linear sum of s many functions in F within ℓ1-distance, one can construct a new function Ampf with O(n) input bits, which cannot be (1/2+sΩ(1))-approximated by F-functions. Taking F to be a function collection containing low-degree F2-polynomials or low-rank F2-matrices, our results are then obtained by first using the algorithmic method to construct a function which is weakly hard against linear sums of F in the above sense, and then applying the derandomized XOR lemma to f. We obtain our new derandomized XOR lemma by giving a generalization of the famous hardcore lemma by Impagliazzo. Our generalization in some sense constructs a non-Boolean hardcore of a weakly hard function f with respect to F-functions, from the weak inapproximability of f by any linear sum of F with bounded ℓp-norm. This generalization recovers the original hardcore lemma by considering the ℓ∞-norm. Surprisingly, when we switch to the ℓ1-norm, we immediately rediscover Levin’s proof of Yao’s XOR Lemma. That is, these first two proofs of Yao’s XOR Lemma can be unified with our new perspective. For proving the correlation bounds, our new derandomized XOR lemma indeed works with the ℓ4/3-norm.
登录
查看更多内容
用于以任意顺序读取一次的分支程序的伪随机生成器
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.1007/978-3-030-79416-3_11
发表时间：
2021
期刊：
2021
影响因子：
--
作者：
Huang, Xuangui;Viola, Emanuele
通讯作者：
Viola, Emanuele
来自非平凡去随机化的几乎所有电路下界
DOI：
10.1109/focs46700.2020.00009
发表时间：
2020
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Chen, Lijie;Lyu, Xin;Williams, R. Ryan
通讯作者：
Williams, R. Ryan
针对多项式的弹性函数的异或引理
DOI：
10.1145/3357713.3384242
发表时间：
2020
期刊：
52nd Annual ACM Symposium on Theory of Computing (STOC
影响因子：
--
作者：
Chattopadhyay, Eshan;Hatami, Pooya;Hosseini, Kaave;Lovett, Shachar;Zuckerman, David
通讯作者：
Zuckerman, David