Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

Abstract

The class $FORMULA[s]\circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be the maximum $k$-party NOF randomized communication complexity of $\mathcal{G}$. We show: (1) The Generalized Inner Product function $GI{P}_n^k$ cannot be computed in $FORMULA[s]\circ \mathcal{G}$ on more than $1/2+\epsilon$ fraction of inputs for $$s=o\left(\frac{n^2}{{\left(k\cdot 4^k\cdot R^{(k)}(\mathcal{G})\cdot \log (n/\epsilon )\cdot \log (1/\epsilon )\right)}^2}\right).$$ As a corollary, we get an average-case lower bound for $GI{P}_n^k$ against $FORMULA[n^{1.99}]\circ PT{F}^{k-1}$. (2) There is a PRG of seed length $n/2+O\left(\sqrt{s}\cdot R^{(2)}(\mathcal{G})\cdot \log (s/\epsilon )\cdot \log (1/\epsilon )\right)$ that $\epsilon$-fools $FORMULA[s]\circ \mathcal{G}$. For $FORMULA[s]\circ LTF$, we get the better seed length $O\left(n^{1/2}\cdot s^{1/4}\cdot \log (n)\cdot \log (n/\epsilon )\right)$. This gives the first non-trivial PRG (with seed length $o(n)$) for intersections of $n$ half-spaces in the regime where $\epsilon \le 1/n$. (3) There is a randomized $2^{n-t}$-time $\#$SAT algorithm for $FORMULA[s]\circ \mathcal{G}$, where $$t=\Omega {\left(\frac{n}{\sqrt{s}\cdot {\log }^2(s)\cdot R^{(2)}(\mathcal{G})}\right)}^{1/2}.$$ In particular, this implies a nontrivial #SAT algorithm for $FORMULA[n^{1.99}]\circ LTF$. (4) The Minimum Circuit Size Problem is not in $FORMULA[n^{1.99}]\circ XOR$. On the algorithmic side, we show that $FORMULA[n^{1.99}]\circ XOR$ can be PAC-learned in time $2^{O(n/\log n)}$.