# Oblivious Turing Machine emulation lower bound

Is there a proof that the emulation of a Turing machine on an oblivious Turing machine can't be done in less than $$\mathcal{O}\left(m\log m\right)$$ where $$m$$ is the number of steps the Turing machine uses? Or is this just an upper bound?

In the paper of Paul Vitányi about relativized oblivious Turing machines, Vitányi claims

"They [Pippenger and Fischer, 1979] showed that this result cannot be improved in general, since there is a language L wich is recognized by a 1-tape real-time Turing machine $$M$$, and any oblivious Turing machine $$M'$$ recognizing $$L$$ must use at least an order $$O(n \log n)$$ steps".

This should state $$O(m \log m)$$ as an absolute bound. However I don't find any proof of this in

Pippenger, Nicholas; Fischer, Michael J., Relations among complexity measures, J. Assoc. Comput. Mach. 26, 361-381 (1979). ZBL0405.68041.

Any ideas? Furthermore, what is the space complexity of this emulation? As far as I know the conversion to a universal Turing machine only doubles the tape length. Can I assume that the space complexity is $$\mathcal{O}\left(l\right)$$ with $$l$$ the space complexity of the original Turing machine?

• Please match parentheses and define what T is. I think that it is still open, but I am not an expert. – Tsuyoshi Ito Mar 11 '12 at 23:17
• what's an oblivious turing machine ? – Suresh Venkat Mar 12 '12 at 2:22
• An Oblivious Turing Machine is a Turing Machine where the movement of the heads only depends on the length of the input and not the input itself. For instance linear search (if the head keeps moving until it has reached the end of the input) – Willem Van Onsem Mar 12 '12 at 2:42

As mentioned above, it is not known in general if there is a faster oblivious simulation.

But interesting lower bounds for this problem are known, under more constrained conditions. For instance, what if you want an oblivious simulation that preserves not only the time $t$ but also the space usage $s$? Beame and Machmouchi have recently proved an interesting time-space tradeoff lower bound for this problem: either the space must increase by a factor of $n^{1-o(1)}$, or the time must increase by a factor of $\Omega(\log n \cdot \log \log n)$.

The paper is here: http://eccc.hpi-web.de/report/2010/104/

Just an extended comment: I think it is still an open problem; see Lipton and Regan's blog for some nice discussions about improving the result of the Fischer-Pippenger theorem.

For example see the posts: Oblivious Turing Machines and a "Crock" or Circuits Bounds for Turing Machine Computations (both dated 2009).

In the second post they show that a better circuit bound ( $O(n \log {\log n})$) is possible using a partial-boolean function $g:2^n \to \{0,1,*\}$ that approximates the original function $f$ on $2^{n-o(n)}$ inputs.

• I've read the Fischer-Pippenger theorem and it's proof. However never in the proof there is a component that says that this there is no faster method. I was wondering if there exists a proof that says this is the guaranteed minimum. If you look at the proof they emulate the TM on a UTM and then perform a little hack to make it oblivious. However one can argue the first step is only necessary to know how the machine will behave. – Willem Van Onsem Mar 12 '12 at 0:37
• @CommuSoft No one is suggesting that the proof is anything but an upper bound proof. The blog posts suggest that improving on Fischer-Pippenger is an open problem. – Sasho Nikolov Mar 12 '12 at 0:53
• @CommuSoft: It is an open problem ... perhaps a faster method exists or someone will prove that it is the best achievable. – Marzio De Biasi Mar 12 '12 at 0:58
• Well I'm reading a paper published by Paul Vitányi called "Relativized Obliviousness" that seems to claim the time is at least O(m log m). However I'm not quite sure yet if it uses the Fischer-Pippenger theorem to proof this. – Willem Van Onsem Mar 12 '12 at 1:20