Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira
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 number-on-forehead randomized communication complexity of a function in $\mathcal{G}$. Among other results, we show that:
- The Generalized Inner Product function $\mathsf{GIP}^k_n$ cannot be computed in $FORMULA[s]\circ \mathcal{G}$ on more than $1/2+\varepsilon$ fraction of inputs for $$ s = o \! \left ( \frac{n^2}{ \left(k \cdot 4^k \cdot {R}^{(k)}(\mathcal{G}) \cdot \log (n/\varepsilon) \cdot \log (1/\varepsilon) \right)^{2}} \right). $$ This significantly extends the lower bounds against bipartite formulas obtained by \citep{Tal17}. As a corollary, we get an average-case lower bound for $\mathsf{GIP}^k_n$ against $FORMULA[n^{1.99}]\circ PTF^{k-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 \cite{Nis94, Vio15} for circuits with PTF gates.
- There is a PRG of seed length $n/2 + O\left( \sqrt{s} \cdot R^{(2)}(\mathcal{G}) \cdot\log(s/\varepsilon) \cdot \log (1/\varepsilon) \right)$ that $\varepsilon$-fools $FORMULA[s] \circ \mathcal{G}$. For the special case of $FORMULA[s] \circ LTF$, i.e., size-$s$ formulas with LTF (linear threshold function) gates at the bottom, we get the better seed length $O\left(n^{1/2}\cdot s^{1/4}\cdot \log(n)\cdot \log(n/\varepsilon)\right)$. In particular, this provides the first non-trivial PRG (with seed length $o(n)$) for intersections of $n$ half-spaces in the regime where $\varepsilon \leq 1/n$, complementing a recent result of \citep{OST19}.
- There exists 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$.
- The Minimum Circuit Size Problem is not in $FORMULA[n^{1.99}] \circ \mathsf{XOR}$; thereby making progress on hardness magnification, in connection with results from \citep{OPS19, CJW19}. On the algorithmic side, we show that the concept class $FORMULA[n^{1.99}] \circ \mathsf{XOR}$ can be PAC-learned in time $2^{O(n/\log n)}$.
Versions
- ECCC TR20-018 full version (ECCC report)