Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials
复制标题
恒定深度电路和多项式的量化去随机化的改进界限
作者：
R. Tell
这项工作研究了Goldreich和Wigderson（STOC 2014）提出的量化去随机化问题。一般的量化去随机化问题如下：对于一个电路类$${mathcal{C}}$$C和一个参数B=B（n），给定一个电路$${Cinmathcal{C}}$$C∈C，有n个输入位，决定C是否拒绝所有的输入，或者接受除了B（n）之外的所有输入。在目前的工作中，我们考虑这个问题的三个设置。在每个设置中，我们使参数设置更接近，我们可以无条件地构建相对快速的量化去随机化算法，以及任何量化去随机化算法都意味着类似于标准去随机化算法的“阈值”值（参数）。对于恒定深度的电路，我们构建了一个量化去随机化的算法，该算法适用于仅略小于“阈值”参数的参数B（n），并且明显快于目前已知的最好的标准去随机化算法。在此结果的方式，我们建立了一个新的去随机化的开关引理，显着改善以前的结果时，公式的宽度是小的。对于恒定深度的电路与奇偶校验门，我们降低了“阈值”的Goldreich和Wigderson从深度五到深度四，并构建算法量化去随机化的剩余类型的分层深度3电路，他们离开作为一个开放的问题。我们还考虑了在大的领域，很少消失，并证明了两个下界的种子长度这样的发电机的多元多项式的命中集生成器的问题。我们的几个证明依赖于一个有趣的技术，我们称之为随机测试技术。直觉上，确定性地找到“好”对象的标准技术是构造一个简单的确定性测试，该测试决定好对象的集合，然后使用伪随机生成器“欺骗”该测试。我们表明，一个类似的方法也可以工作，如果简单的确定性测试被替换为分布在简单的测试，并证明使用分布，而不是一个单一的测试的好处。
This work studies the question of quantified derandomization, which was introduced by Goldreich and Wigderson (STOC 2014). The generic quantified derandomization problem is the following: For a circuit class $${mathcal{C}}$$C and a parameter B=B(n), given a circuit $${Cinmathcal{C}}$$C∈C with n input bits, decide whether C rejects all of its inputs, or accepts all but B(n) of its inputs. In the current work, we consider three settings for this question. In each setting, we bring closer the parameter setting for which we can unconditionally construct relatively fast quantified derandomization algorithms, and the “threshold” values (for the parameters) for which any quantified derandomization algorithm implies a similar algorithm for standard derandomization. For constant-depth circuits, we construct an algorithm for quantified derandomization that works for a parameter B(n) that is only slightly smaller than a “threshold” parameter and is significantly faster than the best currently known algorithms for standard derandomization. On the way to this result, we establish a new derandomization of the switching lemma, which significantly improves on previous results when the width of the formula is small. For constant-depth circuits with parity gates, we lower a “threshold” of Goldreich and Wigderson from depth five to depth four and construct algorithms for quantified derandomization of a remaining type of layered depth-3 circuit that they left as an open problem. We also consider the question of constructing hitting-set generators for multivariate polynomials over large fields that vanish rarely and prove two lower bounds on the seed length of such generators. Several of our proofs rely on an interesting technique, which we call the randomized tests technique. Intuitively, a standard technique to deterministically find a “good” object is to construct a simple deterministic test that decides the set of good objects, and then “fool” that test using a pseudorandom generator. We show that a similar approach works also if the simple deterministic test is replaced with a distribution over simple tests, and demonstrate the benefits in using a distribution instead of a single test.