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

Valentine Kabanets, Sajin Koroth, Zhenjian Lu +2

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}$.…