15

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?

Easier Question (added in v2)

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.)
Robin Kothari
  • 13,617
  • 2
  • 60
  • 116

1 Answers1

-2

there is also a method called the Krapchenko lower bound "which can be slightly larger than Nechiporuks method". see John E Savage, Models of Computation, section 9.4.2. (which is covered right after the Nechiporuk method in section 9.4.1)

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 2
    Thanks for the reference, but Krapchenko's method only works over the De Morgan basis (called the "standard basis" in Savage's book). My question is about the full binary basis. – Robin Kothari Sep 10 '12 at 19:33
  • if Nechiporuks method works over full binary basis & the method is shown to work over the De Morgan/standard basis in Savages book, why doesnt Krapchenkos work over both also? but agreed Savage doesnt have an example of the Krapchenko/full binary basis. – vzn Sep 10 '12 at 20:19
  • 1
    The full binary basis is a superset of the De Morgan basis. Any lower bounds that work against the full binary basis also work against the De Morgan basis. – Robin Kothari Sep 10 '12 at 20:36
  • ok, fine, what rules out the Krapchenko method working on the full binary basis? am suspecting the Nechiporuk method was probably 1st applied to the de Morgan basis & then extended to the full basis, true? what rules that out for the Krapchenko method? – vzn Sep 10 '12 at 20:45