A fixed-depth size-hierarchy theorem for AC0[⊕] via the coin problem
A fixed-depth size-hierarchy theorem for AC0[⊕] via the coin problem
复制标题
通过硬币问题得出 AC0[⊕] 的固定深度大小层次定理
DOI：
10.1145/3313276.3316339
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Venkitesh
中科院分区：
文献类型：
--
作者：
N. Limaye;Karteek Sreenivasaiah;S. Srinivasan;Utkarsh Tripathi;S. Venkitesh
在这项工作中，我们证明了针对一致的\(AC^{0}[\oplus]\)的首个固定深度规模层次定理。特别地，我们表明对于任何固定的\(d\)，具有深度为\(d\)且规模为\(n^{k}\)的一致\(AC^{0}[\oplus]\)公式的函数类\(C_{d,k}\)构成一个无穷层次。我们通过展示第一类显式函数来证明这一点，对于这类\(AC^{0}[\oplus]\)公式的类，我们有近乎（直至一个多项式因子）匹配的上界和下界。这些显式函数源自\(\delta\)-硬币问题，该问题是区分正面朝上概率为\((1 + \delta)/2\)或\((1-\delta)/2\)的硬币的计算问题，其中\(\delta\)是一个趋近于\(0\)的参数。我们研究了这个问题的复杂性，并在上界和下界方面都取得了进展。
上界：对于任何常数\(d\geq2\)，我们表明存在显式单调\(AC^{0}\)公式（即仅由与门和或门组成）来解决\(\delta\)-硬币问题，其深度为\(d\)，规模为\(\exp(O(d(1/\delta)^{1/(d - 1)}))\)，且样本复杂度（即输入数量）为\(\text{poly}(1/\delta)\)。这在规模方面（是最优的）与奥唐奈（O’Donnell）和温默（Wimmer）（ICALP 2007）以及天野（Amano）（ICALP 2009）之前的上界相匹配，并将样本复杂度从\(\exp(O(d(1/\delta)^{1/(d - 1)}))\)改进到\(\text{poly}(1/\delta)\)。
下界：我们表明上述上界即使对于\(AC^{0}[\oplus]\)公式这个强得多的模型（也允许非门和奇偶校验门）在规模方面也近乎是紧的：形式上，我们表明任何解决\(\delta\)-硬币问题的\(AC^{0}[\oplus]\)公式必须具有规模\(\exp(\Omega(d(1/\delta)^{1/(d - 1)}))\)。这加强了沙尔蒂尔（Shaltiel）和维奥拉（Viola）（SICOMP 2010）的一个结果，他们证明了\(AC^{0}[\oplus]\)的一个\(\exp(\Omega((1/\delta)^{1/(d + 2)}))\)下界，以及科恩（Cohen）、加诺尔（Ganor）和拉兹（Raz）（APPROX - RANDOM 2014）对于\(0\)类所展示的\(\exp(\Omega((1/\delta)^{1/(d - 1)}))\)下界。上界是一个涉及使用詹森不等式和经典组合设计的去随机化。下界涉及证明在\(2\)上解决\(\delta\)-硬币问题的多项式的最优次数下界。
In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC0[⊕]. In particular, we show that for any fixed d, the class Cd,k of functions that have uniform AC0[⊕] formulas of depth d and size nk form an infinite hierarchy. We show this by exhibiting the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC0[⊕] formulas. The explicit functions are derived from the δ-Coin Problem, which is the computational problem of distinguishing between coins that are heads with probability (1+δ)/2 or (1−δ)/2, where δ is a parameter that is going to 0. We study the complexity of this problem and make progress on both upper bound and lower bound fronts. Upper bounds. For any constant d≥ 2, we show that there are explicit monotone AC0 formulas (i.e. made up of AND and OR gates only) solving the δ-coin problem that have depth d, size exp(O(d(1/δ)1/(d−1))), and sample complexity (i.e. number of inputs) poly(1/δ). This matches previous upper bounds of O’Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009) in terms of size (which is optimal) and improves the sample complexity from exp(O(d(1/δ)1/(d−1))) to poly(1/δ). Lower bounds. We show that the above upper bounds are nearly tight (in terms of size) even for the significantly stronger model of AC0[⊕] formulas (which are also allowed NOT and Parity gates): formally, we show that any AC0[⊕] formula solving the δ-coin problem must have size exp(Ω(d(1/δ)1/(d−1))). This strengthens a result of Shaltiel and Viola (SICOMP 2010), who prove a exp(Ω((1/δ)1/(d+2))) lower bound for AC0[⊕], and a lower bound of exp(Ω((1/δ)1/(d−1))) shown by Cohen, Ganor and Raz (APPROX-RANDOM 2014) for the class 0. The upper bound is a derandomization involving a use of Janson’s inequality and classical combinatorial designs. The lower bound involves proving an optimal degree lower bound for polynomials over 2 solving the δ-coin problem.
第二傅立叶级伪随机发生器及其在具有奇偶校验门的 AC0 中的应用
DOI：
--
发表时间：
2019
期刊：
(ITCS
影响因子：
--
作者：
Chattopadhyay, Eshan;Hatami, Pooya;Lovett, Shachar;Tal, Avishay
通讯作者：
Tal, Avishay