Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds
Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds
复制标题
加权门消除：二次品种的布尔分散器意味着改进的电路下界
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Kulikov
中科院分区：
文献类型：
--
作者：
Alexander Golovnev;A. Kulikov
在本文中，我们激励研究的布尔分散剂的二次品种，明确建设这样的对象给出了改进的电路下界。（n，k，s）-二次分散子是一个关于n个变量的函数，它在Fn/2的任何子集上都不是常数，该子集的大小至少为s，可以定义为至多k个二次多项式的公共根的集合。本文证明了如果布尔函数f对任意函数g（n）= o（n）是（n，1.83n，2g（n））-二次分散器，则f的电路长度至少为3.11n.为了证明这一点，我们推广了门消除法，使归纳工作的各种规模，而不是在以前已知的证明变量的数量。
In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An (n,k,s)-quadratic disperser is a function on n variables that is not constant on any subset of Fn/2 of size at least s that can be defined as the set of common roots of at most k quadratic polynomials. We show that if a Boolean function f is a (n, 1.83n, 2g(n)-quadratic disperser for any function g(n)=o(n) then the circuit size of f is at least 3.11n. In order to prove this, we generalize the gate elimination method so that the induction works on the size of the variety rather than on the number of variables as in previously known proofs.