<p>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 <em>Fischer-Pippenger theorem</em>.</p>

<p>For example see the posts: <a href="http://rjlipton.wordpress.com/2009/07/28/oblivious-turing-machines-and-a-crock/">Oblivious Turing Machines and a "Crock"</a> or <a href="http://rjlipton.wordpress.com/2009/08/05/circuits-bounds-for-turing-machine-computations/">Circuits Bounds for Turing Machine Computations</a> (both dated 2009).</p>

<p>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 <em>approximates</em>  the original function $f$ on $2^{n-o(n)}$ inputs.</p>

CC BY-SA 3.0
2012-03-12T00:37:39.750Z
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
CC BY-SA 3.0
2012-03-12T00:53:02.593Z
@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
CC BY-SA 3.0
2012-03-12T00:58:26.097Z
@CommuSoft: It is an open problem ... perhaps a faster method exists or  someone will prove that it is the best achievable.
Marzio De Biasi
CC BY-SA 3.0
2012-03-12T01:20:31.403Z
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
CC BY-SA 3.0
2012-03-12T00:25:43.687Z
2012-03-12T00:48:55.047Z
2012-03-12T00:48:55.047Z
Marzio De Biasi
<p>As mentioned above, it is not known in general if there is a faster oblivious simulation.</p>

<p>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)$.</p>

<p>The paper is here: <a href="http://eccc.hpi-web.de/report/2010/104/">http://eccc.hpi-web.de/report/2010/104/</a></p>

CC BY-SA 3.0
2012-03-12T01:19:28.270Z
2012-03-12T01:19:28.270Z
Ryan Williams
<p>Is there a proof that the emulation of a Turing machine on an oblivious Turing machine can't be done in less than <span class="math-container">$\mathcal{O}\left(m\log m\right)$</span> where <span class="math-container">$m$</span> is the number of steps the Turing machine uses? Or is this just an upper bound?</p>

<p>In the paper of Paul Vitányi about relativized oblivious Turing machines, Vitányi claims</p>

<blockquote>
  <p>"They [<a href="http://www.ccs.neu.edu/home/viola/classes/papers/PippengerF-Oblivious.pdf" rel="nofollow noreferrer">Pippenger and Fischer, 1979</a>] 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 <span class="math-container">$M$</span>, and any oblivious Turing machine <span class="math-container">$M'$</span> recognizing <span class="math-container">$L$</span> must use at least an order <span class="math-container">$O(n \log n)$</span> steps".</p>
</blockquote>

<p>This should state <span class="math-container">$O(m \log m)$</span> as an absolute bound. However I don't find any proof of this in </p>

<p><em>Pippenger, Nicholas; Fischer, Michael J.</em>, <a href="http://dx.doi.org/10.1145/322123.322138" rel="nofollow noreferrer"><strong>Relations among complexity measures</strong></a>, J. Assoc. Comput. Mach. 26, 361-381 (1979). <a href="https://zbmath.org/?q=an:0405.68041" rel="nofollow noreferrer">ZBL0405.68041</a>.</p>

<p>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 <span class="math-container">$\mathcal{O}\left(l\right)$</span> with <span class="math-container">$l$</span> the space complexity of the original Turing machine?</p>

CC BY-SA 3.0
2012-03-11T23:17:09.263Z
Please match parentheses and define what T is.  I think that it is still open, but I am not an expert.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-12T02:22:49.093Z
what's an oblivious turing machine ?
Suresh Venkat
CC BY-SA 3.0
2012-03-12T02:42:06.433Z
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
<cc.complexity-theory><turing-machines>
Oblivious Turing Machine emulation lower bound
willeM_ Van Onsem
# Oblivious Turing Machine emulation lower bound

(Asked by: username_0 on 2012-03-11)

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](http://www.ccs.neu.edu/home/viola/classes/papers/PippengerF-Oblivious.pdf)] 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**](http://dx.doi.org/10.1145/322123.322138), J. Assoc. Comput. Mach. 26, 361-381 (1979). [ZBL0405.68041](https://zbmath.org/?q=an:0405.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?

**Tags:** cc.complexity-theory, turing-machines
> **Comments:**
> **username_1**: Please match parentheses and define what T is.  I think that it is still open, but I am not an expert.  
> **username_2**: what's an oblivious turing machine ?  
> **username_0**: 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)  

---

## 2 answers

### Answer by username_5 on 2012-03-12. Score: 20 | Accepted answer

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/>


---

### Answer by username_3 on 2012-03-12. Score: 13

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"](http://rjlipton.wordpress.com/2009/07/28/oblivious-turing-machines-and-a-crock/) or [Circuits Bounds for Turing Machine Computations](http://rjlipton.wordpress.com/2009/08/05/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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: @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.  
> **username_3**: @CommuSoft: It is an open problem ... perhaps a faster method exists or  someone will prove that it is the best achievable.  
> **username_0**: 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.  

---

