Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
share
The class FORMULA[s] ∘𝒢 consists of Boolean functions computable by size-s de Morgan formulas whose leaves are any Boolean functions from a class 𝒢. We give lower bounds and (SAT, Learning, and PRG) algorithms for FORMULA[n^1.99]∘𝒢, for classes 𝒢 of functions with low communication complexity. Let R^(k)(𝒢) be the maximum k-party NOF randomized communication complexity of 𝒢. We show: (1) The Generalized Inner Product function GIP^k_n cannot be computed in FORMULA[s]∘𝒢 on more than 1/2+ε fraction of inputs for s = o ( n^2/(k · 4^k ·R^(k)(𝒢) ·log (n/ε) ·log(1/ε) )^2). As a corollary, we get an average-case lower bound for GIP^k_n against FORMULA[n^1.99]∘ PTF^k-1. (2) There is a PRG of seed length n/2 + O(√(s)· R^(2)(𝒢) ·log(s/ε) ·log (1/ε) ) that ε-fools FORMULA[s] ∘𝒢. For FORMULA[s] ∘ LTF, we get the better seed length O(n^1/2· s^1/4·log(n)·log(n/ε)). This gives the first non-trivial PRG (with seed length o(n)) for intersections of n half-spaces in the regime where ε≤ 1/n. (3) There is a randomized 2^n-t-time #SAT algorithm for FORMULA[s] ∘𝒢, where t=Ω(n/√(s)·log^2(s)· R^(2)(𝒢))^1/2. In particular, this implies a nontrivial #SAT algorithm for FORMULA[n^1.99]∘ LTF. (4) The Minimum Circuit Size Problem is not in FORMULA[n^1.99]∘ XOR. On the algorithmic side, we show that FORMULA[n^1.99] ∘ XOR can be PAC-learned in time 2^O(n/log n).
READ FULL TEXT