Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the known case analyses can also be used to prove average case circuit lower bounds, that is, lower bounds on the size of approximations of an explicit function.In this paper, we provide a general framework for proving worst/average case lower bounds for circuits and upper bounds for #SAT that is built on ideas of Chen and Kabanets. A proof in such a framework goes as follows. One starts by fixing three parameters: a class of circuits, a circuit complexity measure, and a set of allowed substitutions. The main ingredient of a proof goes as follows: by going through a number of cases, one shows that for any circuit from the given class, one can find an allowed substitution such that the given measure of the circuit reduces by a sufficient amount. This case analysis immediately implies an upper bound for #SAT. To~obtain worst/average case circuit complexity lower bounds one needs to present an explicit construction of a function that is a disperser/extractor for the class of sources defined by the set of substitutions under consideration. We show that many known proofs (of circuit size lower bounds and upper bounds for #SAT) fall into this framework. Using this framework, we prove the following new bounds: average case lower bounds of 3.24n and 2.59n for circuits over U_2 and B_2, respectively (though the lower bound for the basis B_2 is given for a quadratic disperser whose explicit construction is not currently known), and faster than 2^n #SAT-algorithms for circuits over U_2 and B_2 of size at most 3.24n and 2.99n, respectively. Here by B_2 we mean the set of all bivariate Boolean functions, and by U_2 the set of all bivariate Boolean functions except for parity and its complement.
展开▼
机译：具有无限深度的二进制布尔电路的大多数已知下界已通过门消除方法得到证明。对于二进制布尔电路上的#SAT问题，最有效的已知算法使用与门消除中相似的案例分析。 Chen和Kabanets最近表明，已知的案例分析还可以用于证明平均案例电路的下界，即显式函数近似值的下界。本文提供了证明最差/平均电路的下限和#SAT的上限（基于Chen和Kabanets的思想）。在这样的框架中的证明如下。首先确定三个参数：一类电路，电路复杂性度量和一组允许的替换。证明的主要内容如下：通过研究许多案例，可以看出，对于给定类别的任何电路，人们都可以找到允许的替代，从而使给定的电路度量减少足够的数量。这种案例分析立即暗示了#SAT的上限。为了获得最坏/平均情况下的电路复杂性下限，需要呈现一种函数的显式构造，该函数是所考虑的一组替换所定义的源类别的分散器/提取器。我们表明，许多已知的证明（电路大小的下限和上限为#SAT）都属于此框架。使用这个框架，我们证明了以下新的界限：U_2和B_2上的电路的平均情况下界分别为3.24n和2.59n（尽管基B_2的下界是针对目前尚不明确构造的二次分散器给出的）并且对于大小最大为3.24n和2.99n的U_2和B_2上的电路，其速度比2 ^ n #SAT算法快。在这里，由B_2表示所有双变量布尔函数的集合，由U_2表示除奇偶校验及其补码之外的所有双变量布尔函数的集合。
展开▼
