# Implication of lower bounds in Boolean circuit to other models of computation

Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$.

Then, how strong can we say about how hard $f$ is in other models? The other models are, for example, pointer machine or Word RAM model, or decision tree.

Can we get a lower bound of $n^{t-1}$ or even $\tilde{\Omega}(n^t)$ for instance ?

• You can construct a size $O(T)$ circuit from a $O(T)$ time bounded deterministic Turing machine with constant number of tapes. – Sasho Nikolov Nov 13 '14 at 0:22
• @SashoNikolov Do you mean a size $O(T \log T)$ circuit? – Alexander S. Kulikov Nov 19 '14 at 13:48
• @AlexanderS.Kulikov Right, I was sloppy, sorry about that. I guess the trivial construction gives $O(T^2)$, and more efficient ones give $O(T\log T)$. – Sasho Nikolov Nov 19 '14 at 18:00