1
$\begingroup$

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 ?

$\endgroup$
  • 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$ – Sasho Nikolov Nov 13 '14 at 0:22
  • $\begingroup$ @SashoNikolov Do you mean a size $O(T \log T)$ circuit? $\endgroup$ – Alexander S. Kulikov Nov 19 '14 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$ – Sasho Nikolov Nov 19 '14 at 18:00

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.