期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-44
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The class FORMULA[s] ◦ G consists of Boolean functions computable by size-s de Morgan formulas whose leaves are any Boolean functions from a class G. We give lower bounds and (SAT, Learning, and PRG) algorithms for FORMULA[n 1.99] ◦ G, for classes G of functions with low communication complexity. Let R(k) (G) be the maximum k-party number-on-forehead randomized communication complexity of a function in G. Among other results, we show that: • The Generalized Inner Product function GIPk n cannot be computed in FORMULA[s] ◦ G on more than 1/2 ε fraction of inputs for s = o n 2 k · 4 k · R(k)(G) · log(n/ε) · log(1/ε) 2 ! . This significantly extends the lower bounds against bipartite formulas obtained by [Tal17]. As a corollary, we get an average-case lower bound for GIPk n against FORMULA[n 1.99] ◦ PTFk−1 , i.e., sub-quadratic-size de Morgan formulas with degree-(k − 1) PTF (polynomial threshold function) gates at the bottom. Previously, only sub-linear lower bounds were known [Nis94, Vio15] for circuits with PTF gates. • There is a PRG of seed length n/2 O √ s · R(2)(G) · log(s/ε) · log(1/ε) that ε-fools FORMULA[s] ◦ G. For the special case of FORMULA[s] ◦ LTF, i.e., size-s formulas with LTF (linear threshold function) gates at the bottom, we get the better seed length O n 1/2 · s 1/4 · log(n) · log(n/ε) . In particular, this provides the first non-trivial PRG (with seed length o(n)) for intersections of n half-spaces in the regime where ε ≤ 1/n, complementing a recent result of [OST19]. • There exists a randomized 2n−t -time #SAT algorithm for FORMULA[s] ◦ G, where t = Ω n √ s · log2 (s) · R(2)(G) 1/2 . In particular, this implies a nontrivial #SAT algorithm for FORMULA[n 1.99] ◦ LTF. • The Minimum Circuit Size Problem is not in FORMULA[n 1.99] ◦ XOR; thereby making progress on hardness magnification, in connection with results from [OPS19, CJW19]. On the algorithmic side, we show that the concept class FORMULA[n 1.99] ◦ XOR can be PAC-learned in time 2O(n/ log n).
