# Characterization of read-once formulae over the full binary basis

Background

A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (which has the 2-bit gates AND and OR, and the 1-bit gate NOT) and the full binary basis (which has all 2-bit gates).

So for example, the AND of 2 bits can be written as a read-once formula over either basis, but the parity of 2 bits cannot be written as a read-once formula over the De Morgan basis.

The set of all functions that can be written as a read-once formula over the De Morgan basis has a combinatorial characterization. See, for example, Combinatorial characterization of read-once formulae by M. Karchmer , N. Linial , I. Newman , M. Saks , A. Wigderson.

Question

Is there an alternate characterization of the set of functions that can be computed by a read-once formula over the full binary basis?

While I'm still interested in an answer to the original question, since I haven't received any answers I thought I'll ask an easier question: What are some lower bound techniques that work for formulae over the full binary basis? (Other than the ones I list below.)

Note that now I'm trying to lower bound the formula size (= number of leaves). For read-once formulae, we have formula size = number of inputs. So if you can prove that a function needs a formula of size strictly greater than n, then that also means it cannot be represented as a read-once formula.

I'm aware of the following techniques (along with a reference for each technique from Boolean Function Complexity: Advances and Frontiers by Stasys Jukna):

• Nechiporuk's method for universal functions (Sec 6.2): Shows an $n^{2-o(1)}$ size lower bound for a certain function. This doesn't help you find lower bounds for a particular function that you might be interested in though.
• Nechiporuk's theorem using subfunctions (Sec 6.5): This is a proper lower bound technique in the sense that it will provide a lower bound for any function you're interested in. For example it shows that any formula over the full binary basis that represents the element distinctness function has size $\Omega(n^2/\log n)$. (And this is the largest lower bound the technique can prove — for any function.)
• have you looked into BDDs, binary decision diagrams? arent they fairly close in complexity? but, havent seen a spec ref on the subj. – vzn Sep 10 '12 at 17:33