A Boolean function is said to be read-once if there is a Formula (a Boolean circuit where every gate has fanout at most $1$) computing the function $f$ such that every variable appears only once in the formula. Since each variable appears only once in the formula so it appears that this can be represented by a very small circuit of constant depth but I have a proof which contradicts my belief. I cannot get a feel of this statement.

(Proof of Read-once $\notin AC^0$)

Suppose read-once $\in AC^0$.

Consider a circuit in $NC^1$ and replace all the repeated literals with new variables $y_1, y_2 \ldots y_t$. Now this is a read-once function. We will now get the $AC^0$ circuit and replace back the $y_i$'s and get $AC^0$ circuit for an $NC^1$ circuit which shows that $AC^0 = NC^1$. Hence the contradiction.

I am still not getting a feel why read-once functions don't have small circuits. I will appreciate if you can give an example of read-once function for which I can't construct an $AC^0$ circuit.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.