ECCC-Report TR10-104https://eccc.weizmann.ac.il/report/2010/104Comments and Revisions published for TR10-104en-usThu, 21 Apr 2011 03:08:15 +0300
Revision 3
| Making RAMs Oblivious Requires Superlogarithmic Overhead |
Widad Machmouchi,
Paul Beame
https://eccc.weizmann.ac.il/report/2010/104#revision3We prove a time-space tradeoff lower bound of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for
randomized oblivious branching programs to compute $1GAP$, also
known as the pointer jumping problem, a problem for which there is a
simple deterministic time $n$ and space $O(\log n)$ RAM (random
access machine) algorithm.
We give a similar time-space tradeoff of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right)$ for
Boolean randomized oblivious branching programs computing
$\GIPshuffle$, a variation of the generalized inner product problem that
can be computed in time $n$ and space $O(\log^2 n)$ by a
deterministic Boolean branching program.
These are also the first lower bounds for randomized oblivious
branching programs computing explicit functions that apply for
$T=\omega(n\log n)$.
They also show that any simulation of
general branching programs by randomized oblivious ones requires either
a superlogarithmic increase in time
or an exponential increase in space.Thu, 21 Apr 2011 03:08:15 +0300https://eccc.weizmann.ac.il/report/2010/104#revision3
Comment 1
| Making Branching Programs Oblivious Requires Superlogarithmic Overhead |
Widad Machmouchi,
Paul Beame
https://eccc.weizmann.ac.il/report/2010/104#comment1In contrast to the claim in the original version of our paper, the
model considered by Ajtai is incomparable to the one that we
consider here. (The same applies to Damgaard and Nielsen's
simulation to the extent that we understand it.)
Russell Impagliazzo brought to our attention that the randomized
oblivious branching programs we are considering are less general
than the oblivious randomized algorithms that Ajtai's simulation
uses. The main difference is that, in our model, for each fixing of
the random choices, the sequence of locations accessed must be
independent of the input though that sequence may depend on the
random choices, while in Ajtai's simulation, it is only necessary
that the {\em probability distribution} of the sequence of locations
accessed is input independent. Upon further investigation, we found
that Ajtai's simulation assumes that the original RAM algorithm only
has sequential access to its input, in which case the small space
upper bound for $1GAP_n$ does not apply (or alternatively the
original RAM algorithm has random access but at least linear space
which a deterministic oblivious branching program can use to
compute any function in linear time). Therefore, the upper bound
derived by Ajtai no longer applies in our model.
In our revised version of the paper, we derive the same
quantitative separation between general and randomized oblivious
algorithms in the case of Boolean inputs, a result that does not
follow from the separation for $1GAP_n$. We obtain this by
considering a variation of the $GIP$ problem, $GIP$-$MAP$ which
includes a pseudorandom permutation on the input bits of $GIP$ as
part of its input. To more accurately represent our results and to
avoid any confusion about their applicability we have changed the
title of our paper slightly.
Sun, 26 Dec 2010 15:21:10 +0200https://eccc.weizmann.ac.il/report/2010/104#comment1
Revision 2
| Making Branching Programs Oblivious Requires Superlogarithmic Overhead |
Widad Machmouchi,
Paul Beame
https://eccc.weizmann.ac.il/report/2010/104#revision2We prove a time-space tradeoff lower bound of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for
randomized oblivious branching programs to compute $1GAP$, also
known as the pointer jumping problem, a problem for which there is a
simple deterministic time $n$ and space $O(\log n)$ RAM (random
access machine) algorithm.
We give a similar time-space tradeoff of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right)$ for
Boolean randomized oblivious branching programs computing
$\GIPshuffle$, a variation of the generalized inner product problem that
can be computed in time $n$ and space $O(\log^2 n)$ by a
deterministic Boolean branching program.
These are also the first lower bounds for randomized oblivious
branching programs computing explicit functions that apply for
$T=\omega(n\log n)$.
They also show that any simulation of
general branching programs by randomized oblivious ones requires either
a superlogarithmic increase in time
or a very substantial increase in space.Thu, 16 Dec 2010 07:01:25 +0200https://eccc.weizmann.ac.il/report/2010/104#revision2
Revision 1
| Making RAMs Oblivious Requires Superlogarithmic Overhead |
Widad Machmouchi,
Paul Beame
https://eccc.weizmann.ac.il/report/2010/104#revision1We prove a time-space tradeoff lower bound of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for
randomized oblivious branching programs to compute $1GAP$, also
known as the pointer jumping problem, a problem for which there is a
simple deterministic time $n$ and space $O(\log n)$ RAM (random
access machine) algorithm.
We give a similar time-space tradeoff of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right)$ for
Boolean randomized oblivious branching programs computing
$\GIPshuffle$, a variation of the generalized inner product problem that
can be computed in time $n$ and space $O(\log^2 n)$ by a
deterministic Boolean branching program.
These are also the first lower bounds for randomized oblivious
branching programs computing explicit functions that apply for
$T=\omega(n\log n)$.
They also show that any simulation of
general branching programs by randomized oblivious ones requires either
a superlogarithmic increase in time
or a very substantial increase in space.Thu, 16 Dec 2010 06:56:48 +0200https://eccc.weizmann.ac.il/report/2010/104#revision1
Paper TR10-104
| Making RAMs Oblivious Requires Superlogarithmic Overhead |
Widad Machmouchi,
Paul Beame
https://eccc.weizmann.ac.il/report/2010/104We prove a time-space tradeoff lower bound of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for
randomized oblivious branching programs to compute $1GAP$, also
known as the pointer jumping problem, a problem for which there is a
simple deterministic time $n$ and space $O(\log n)$ RAM (random
access machine) algorithm.
In a STOC 2010 paper, Ajtai (and independently, Damg{\aa}rd,
Meldgaard, and Nielsen) derived simulations of general RAMs by
randomized oblivious RAMs with only a polylogarithmic factor
increase in time and space. Our lower bound implies that a
superlogarithmic factor increase is indeed necessary in any such
simulation.
Tue, 29 Jun 2010 03:04:09 +0300https://eccc.weizmann.ac.il/report/2010/104