15
$\begingroup$

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.)
Improve this question
$\endgroup$
1
  • $\begingroup$ have you looked into BDDs, binary decision diagrams? arent they fairly close in complexity? but, havent seen a spec ref on the subj. $\endgroup$
    – vzn
    Sep 10, 2012 at 17:33

1 Answer 1

Reset to default
-2
$\begingroup$

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)

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Sep 10, 2012 at 19:33
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Sep 10, 2012 at 20:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Sep 10, 2012 at 20:36
  • $\begingroup$ 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? $\endgroup$
    – vzn
    Sep 10, 2012 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.