Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-018 | 18th February 2020 20:27

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



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:

(1) The Generalized Inner Product function $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 [Tal17]. As a corollary, we get an average-case lower bound for $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 [Nis94, Vio15] for circuits with PTF gates.

(2) 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 [OST19].

(3) 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$.

(4) The Minimum Circuit Size Problem is not in $FORMULA[n^{1.99}] \circ 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}] \circ XOR$ can be PAC-learned in time $2^{O(n/\log n)}$.

ISSN 1433-8092 | Imprint