Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carvalho Lima Oliveira · ACM Transactions on Computation Theory · 2021
The class FORMULA[s]∘G consists of Boolean functions computable by size-sDe Morgan formulas whose leaves are any Boolean functions from a class G. We givelower boundsand (SAT, Learning, andpseudorandom generators(PRGs))algorithmsfor FORMULA[n1.99]∘G, for classes G of functions withlow communication complexity. Let R(k)G be the maximumk-party number-on-forehead randomized communication complexity of a function in G. Among other results, we show the following: • The Generalized Inner Product function GIPkncannot be computed in FORMULA[s]° G on more than 1/2+ε fraction of inputs for s=o(n2/k⋅4k⋅R(k)(G)⋅log(n/ε)⋅log(1/ε))2). This significantly extends the lower bounds against bipartite formulas obtained by [62]. As a corollary, we get an average-case lower bound for GIPknagainst FORMULA[n1.99]∘PTFk−1, i.e., sub-quadratic-size De Morgan formulas with degree-k-1)PTF(polynomial threshold function) gates at the bottom. Previously, it was open whether a super-linear lower bound holds for AND of PTFs. • 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-sformulas withLTF(linear threshold function) gates at the bottom, we get the better seed length O(n1/2⋅s1/4⋅log(n)⋅log(n/ε)). In particular, this provides the first non-trivial PRG (with seed length o(n)) for intersections ofnhalfspaces in the regime where ε≤1/n, complementing a recent result of [45]. • There exists a randomized 2n-t#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[n1.99]∘LTF. • The Minimum Circuit Size Problem is not in FORMULA[n1.99]∘XOR; thereby making progress on hardness magnification, in connection with results from [14, 46]. On the algorithmic side, we show that the concept class FORMULA[n1.99]∘XOR can be PAC-learned in time 2O(n/log n).