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 ?

  • 1
    $\begingroup$ You can construct a size $O(T)$ circuit from a $O(T)$ time bounded deterministic Turing machine with constant number of tapes. $\endgroup$ Nov 13, 2014 at 0:22
  • $\begingroup$ @SashoNikolov Do you mean a size $O(T \log T)$ circuit? $\endgroup$ Nov 19, 2014 at 13:48
  • $\begingroup$ @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)$. $\endgroup$ Nov 19, 2014 at 18:00


Your Answer

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