% Version, Jeff's April 2009

\input{pre.tex}
\title{Some Quick Ideas}
\author{}
\maketitle

\newcommand{\wi}{\widehat{i}}
\newcommand{\I}{\Phi}
% Conjecture
\newtheorem{CJ}{Conjecture}
\newcommand{\cj}[1]{\begin{CJ} \label{#1}}
\newcommand{\ecj}{\end{CJ}}
\newcommand{\repcj}[2]{\noindent {\bf Conjecture}~\ref{#1} {\em #2}}
\newcommand{\rcj}[1]{Conjecture~\ref{#1}}
\newcommand{\pfcj}[1]{\noindent {\bf ``Proof'' of Conjecture \ref{#1}:\ }}
\newcommand{\rsec}[1]{Section~\ref{#1}}
\newcommand{\epf}{$\Blacksquare$}
\newcommand{\Blacksquare}{\rule{.8em}{.8em}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

\bd

\i[Sashka's Technique applied to pFBP] The key step in Sashka and
Russel's technique to prove lower bounds for pFBT was to prove that
for each path $p$ of length $\ell$, $\Pr_{I}[ S(I) \vdash PS_p\ |\ I
\vdash PI_p ] \le {1 \over f}$.  We extend this to a technique for
pFBP.  The key step is to prove that for each node $v$ at depth
$\ell$, $\Pr_{I}[ S(I) \vdash PS_v\ |\ I \vdash PI_v ] \le {1 \over
f}$. My intuition was that $\Pr_{I}[ S(I) \vdash PS_v\ |\ I \vdash
PI_v ] \le \max_{p \in v} \Pr_{I}[ S(I) \vdash PS_p\ |\ I \vdash PI_p
]$. However, in general this is not true.  See Section~\ref{sec sashka
pFBP}

\i[Tree Width vs Parallel Width:] 
I have often explained the pBT model by saying that it can have $w$
different solutions going at a time. But this is not really correct.
Allan was wondering about the power of {\em tree width} verses that of
{\em parallel width}.  The first is the pFBT concept defined before,
while the later imposes a restriction that all of the branches start
at the beginning of the computation and survive until the
end. Essentially, the computation consists of $W$ independent parallel
priority computations, resulting in the best of these. We prove that
there is a problem that can be done with tree width $W=2$, but that
requires parallel width $W = 2^{\Omega(n)}$. It is analogous to many
instances of a problem solved in serial being able to reusing its
bounded memory, while the memory requirements blow up when the
instances must be solved in parallel.  See \rsec{sec Parallel Width}.
The upper bound given below also shows the power of
the tree model to reuse width.

\i[Large Data Items:] A complaint about the priority model has been
that the results depend too much on the input representation. To
address this, we define a model that allows the algorithm to address
as much local information about an object as it wants before it is
forced into an irrevocable decision about it. With in this model, we
are able to prove two tight lower bounds, one on 3-SAT (see
\rsec{large}) and one on a version of the Steiner tree problem (or
$st$-connectivity) (see \rsec{cleanup}).

\i[Extra Info:] Allan and I discussed giving the pFBT algorithm bits
of information about the input before it began. For example, it may be
helpful to give away the number of nodes in the instance. We noted,
however, that giving away $k(n)$ bits can be implemented by having
$2^{k(n)}$ times the width in the tree. Hence, a $2^{\Omega{n}}$ lower
bound on the width automatically gives a lower bound with $k(n) =
\bigO(n)$. 

\ed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Sashka's Technique applied to pFBP} \label{sec sashka pFBP}

We will now attempt to apply Sashka and Russell's lower bound
technique to the pFBP model. Assume that the $q$ value for each node
is binary and monotone increasing moving back up the DAG.

A path $p$ of length $\ell$ in the $DAG_A$ specifies $PI_p =
\left<PI_p^{in}, PI_p^{out}\right>$ and $PS_p$ where $PI_p^{in}$ is
the set of $\ell$ data items that are known to be in the instance,
$PI_p^{out}$ is the set of data items that are known not to be in the
instance, and $PS_p$ specifies the decisions made about each data item
in $PI^{in}$.  Define $I \vdash PI_p$ to mean that instance $I$
travels down path $p$, i.e.\ this path is in $DAG_A(I)$, because $I$
is consistent with $PI_p$, i.e.\ contains the data items in
$PI_p^{in}$ and not those in $PI_p^{out}$.  Define $S(I) \vdash PS_p$
to mean that the decisions made about each data item in $PI_p^{in}$ is
consistent with the/a solution for $I$.  There technique for pFBT was
to prove that $\forall p,\ \Pr_{I}[ S(I) \vdash PS_p\ |\ I \vdash PI_p
] \le {1 \over f}$.


Let $v$ be a node at level $\ell$ in the DAG. It is labeled with
$\left<PI_v,PS_v\right>$, where $PI_v = \left< PI_p\| \ p \mbox{ is a
path to } v \right>$ and $PS_v = \left< PS_p\| \ p \mbox{ is a path to
} v \right>$.  Define $I \vdash PI_v$ to mean that instance $I$
travels though node $v$, i.e.\ node $v$ is in $DAG_A(I)$, because $I$
is consistent with at least one of the paths $p$ to it, i.e.\ $OR_{p
\in v} \left[ I \vdash PI_p \right]$.  Consider any such instance $I$,
if there is a path in $DAG_A(I)$ leading from node $v$ to an accepting
node, i.e.\ to a sink node labeled one, then all the nodes in the DAG
from this accepting node to $v$ and back up through every path in
$DAG_A(I)$ to the root will all be labeled one. The adversary might
choose any of these paths $p$ from the root back down to node $v$ and
on to the accepting node. Hence, $PS_p$ must be a valid partial
solution for $I$ for each such paths. Note that $PS_{p'}$ does not
need to be a valid partial solution for $I$ if this path is in $DAG_A$
but not in $DAG_A(I)$.  Define $S(I) \vdash PS_v$ if this is the case,
i.e.\ $AND_{p \in v} \left[ I \vdash PI_p\ \Rightarrow\ S(I) \vdash
PS_p \right]$.

\begin{thm} \label{sashka DAG} \mbox{}
\be
\i Give a probability distribution on instances $I$.  
\i Prove that whp every set $PI_p^{out}$ in $DAG_A(I)$ is
``small''. (Assume from here on in that this is the case.)
\i Prove that $\forall v,\ \Pr_{I}[ S(I) \vdash PS_v\ |\ I \vdash
  PI_v ] \le {1 \over f}$.
\ee
The theorem then assures that any valid pFBP has width $w \ge f$.
\end{thm}

\begin{proof} of Theorem~\ref{sashka DAG} 
The challenge is that for each instances $I$, there is a possibly
different $DAG_A(I)$.

\medskip
\noindent
{\bf Define:} $Tried = \left\{ \left<I,v \right>\ |\ I \vdash PI_v \right\}$.

\begin{lemma} \label{tried}
$|Tried| \le w \cdot \left|\{I\}\right|$.
\end{lemma}

\begin{proof} of Lemma~\ref{tried}
Every instance $I$ has at most $w$ nodes at level $\ell$. 
\end{proof}

\medskip
\noindent
{\bf Define:} $Succeed = \left\{ \left<I,v\right>\ |\ 
I \vdash PI_v \mbox{ and } S(I) \vdash PS_v \right\}$. 

\begin{lemma} \label{succeed big}
$|Succeed| \ge \left|\{I\}\right|$
\end{lemma}

\begin{proof} of Lemma~\ref{succeed big}
Every instance $I$ needs at least one path on which it succeeds and
the node $v$ at level $\ell$ along this path
will be such that $\left<I,v\right> \in Succeed$.
\end{proof}

\begin{lemma} \label{succeed small}
$|Succeed| \le {1 \over f} \cdot |Tried|$
\end{lemma}

\begin{proof} of Lemma~\ref{succeed small}
By step 3, 
\begin{eqnarray*}
|Succeed| & = & \sum_v
\left| \left\{ \left<I,v\right>\ |\ I \vdash PI_v \mbox{ and } S(I) \vdash PS_v \right\} \right| \\
& = & \sum_v
\Pr_I \left[ I \vdash PI_v \mbox{ and } S(I) \vdash PS_v \right]
\cdot \left| \left\{ I \right\} \right| \\
& = & \sum_v
\Pr_I \left[ S(I) \vdash PS_v\ |\ I \vdash PI_v  \right] \cdot
\Pr_I \left[ I \vdash PI_v \right]
\cdot \left| \left\{ I \right\} \right| \\
& \le & \sum_v
{1 \over f} \cdot
\Pr_I \left[ I \vdash PI_v \right]
\cdot \left| \left\{ I \right\} \right| \\
& \le & {1 \over f} \cdot \sum_v
\left| \left\{ \left<I,v\right>\ |\ I \vdash PI_v \right\} \right| \\
& = & {1 \over f} \cdot |Tried|
\end{eqnarray*}
\end{proof}

\noindent
By Lemma~\ref{succeed big}, Lemma~\ref{succeed small}, and 
Lemma~\ref{tried}, we have that 
$\left|\{I\}\right| \le |Succeed| 
\le {1 \over f} \cdot |Tried|
\le {1 \over f} \cdot w \cdot \left|\{I\}\right|$.
Hence, $w \ge f$ as needed.
\end{proof}

\medskip
\noindent
{\bf Shortest Path} can be done in poly-time in pFBP but not in pFBT.
This (I believe) is because $\Pr_{I}[ S(I) \vdash PS_p\ |\ I \vdash
PI_p ] \le {1 \over f}$ is not true for specially cooked sets
$\left<PI_p,PS_p\right>$, even though it is true for the sets that
arise in practice. For example, suppose that $PI_p^{in}$ said that
there is a partial path of surprisingly low (or high) weight in the
graph and $PS_p$ said that that path is (is not) in the solution. Then
they would probably be right.

If pFBP is more powerful then pFBT, then it is because it pFBP is able
to find such situations, where pFBT is not.

\medskip
\noindent
The next conjecture lets us reuse for pFBP many pFBT lowerbounds proofs
without modification.

\cj{pf}
$\Pr_{I}[ S(I) \vdash PS_v\ |\ I \vdash
PI_v ] \le (\ell+1) \max_{p \in v} \Pr_{I}[ S(I) \vdash PS_p\ |\ I \vdash PI_p
]$. 
\ecj

I am quite sure it is true. $S(I) \vdash PS_v$ consists of a big AND,
requiring many conditions of the form $S(I) \vdash PS_p$. The
probability all of them are true is clearly smaller than the
probability that only one is true. For intuition lets change this
condition to simply that the algorithm needs to know what decision to
make for $\l$ of the data items (but it does not matter which).
Suppose the algorithm has been told $I \vdash PI_v$. This is a big
OR. Telling it $I \vdash PI_p$ is more information. Surely telling it
more information before needing to guess the decisions for the $\l$
data items can only help. Especially, since, the $p \in v$ is chosen
to be the most useful.

I thought it was true for sure but here is why it might not be.  Let
$S_p = \{I\ |\ I \vdash PI_p \}$. Think of $\{S_p\ |\ p \in v\}$ as
being a collection of sets of red and blue balls.  The ball $I$ is red
if $S(I) \vdash PS_v$.  For each $i$, $q_p = {|S_p \cap red| \over
|S_p|}$ is the density of red balls in the $i^{th}$ set and $q =
{|(\cup_p S_p) \cap red| \over |(\cup_p S_p)|}$ is the density red
balls over all. My intuition was that $q \le \max_p q_p$. However,
this is not true.  Let there be $m$ sets. Each $S_p$ consist of $q'n$
red balls that are not contained in any other set and of $(1-q')n$
blue balls that are common to every set.  Then the density of each
$S_p$ is $q_p = q'$. The total number of red balls is $m \cdot q'n$
and the total number of blue balls is $1 \cdot (1-d')n$ giving an over
all density of ${md'n \over mq'n + (1-q')n} \approx 1$.  This is
counter example to \rcj{pf}. It, however, requires lots of
intersection between the sets $S_p$ on the blue balls. The next lemma,
however, proves that this cant happen because the intersections are
small while the number of blue balls huge.

To make things slightly easier, lets assume that the data items in
each instance are indexed from one to $n$, i.e.\ $I \in \Pi_{i \in
[n]} D_i$.  Recall that $PI_p^{in}$ fixes the values in $I$ for a
subset of these indexes and that $PI_p^{out}$ throws out possibilities
for the remaining indexes, i.e.\ $S_p = \{I\ |\ I \vdash PI_p \} =
PI_p^{in} \times \Pi_{i \in [n]-PI_p^{in}} D_{\left<p,i\right>}$,
where $D_{\left<p,i\right>} = D_i -PI_{\left<p,i\right>}^{out}$ is the
set of values still possible for this index.  Because the path $p$ is
not {\em bad}, for each $i \in [n]-PI_p^{in}$, $|D_{\left<p,i\right>}|
\ge {|D_i| \over e^{2 \e^2n}}$.  Let us denote this size as $d$.

\begin{lemma} \label{overlap} (1) If $PI_p^{in}$ and $PI_{p'}^{in}$ do not fix the same
set of indexes (or fix the same set of indexes but in different ways),
then $|S_p \cap S_{p'}| \le {1 \over d} \max(|S_p|,|S_{p'}|)$.  (2) If
$PI_p^{in}$ and $PI_{p'}^{in}$ fix the same
set of indexes in the same way, the difference between $S_p$ and
$S_{p'}$ depends only on the $PI_p^{out}$ and **** we will ignore this case
from here on in. ****
\end{lemma}

\begin{proof} of Lemma~\ref{overlap} If there is some index $i$, where the $i^{th}$ value in
$I$ is fixed in $S_p$ or in $S_{p'}$, but not in the other. Hence,
$|S_p \cap S_{p'}| \le {1 \over d} \max(|S_p|,|S_{p'}|)$.  
\end{proof}

\cj{worst}
I believe the following is the worst case.
\ecj

\noindent
We start by colouring a small number of the balls ``red''. Let $S(I)
\vdash PS_p$ be true for $I$ if $I_i = 0$ for at least one $i \le
\ell+1$. We want the sets $S_p$ to not over lap on these red balls but
over lap a lot everywhere else. For each $\wi \le \ell+1$, and for
each $\alpha \in \Pi_{i \in [\ell+1]-\wi} [D_i-0]$, let there be a
path $p$ such that $PI_p^{in}$ fix the indexes $i \in [\ell+1]-\wi$ of
$I$ to be the nonzero values $\alpha$. This gives $S_p = \{I\ |\ I
\vdash PI_p \} = \alpha \times \Pi_{i \in [n]-[\ell+1]+\wi}
D_i$. Note that the only way for $I \in S_p$ to be
red is to have a zero at index $\wi$.  This gives that $\Pr_{I}[ S(I)
\vdash PS_p\ |\ I \vdash PI_p ] = {1 \over d}$.  On the other hand,
$\cup_{p \in v} S_p$ is almost the full domain of possible
instances. The only restriction is that the first $\ell+1$ indexes
have at most one zero. There are still $\ell+1$
indexes such that if this index is zero then $I$ is red.  This gives
that $\Pr_{I}[ S(I) \vdash PS_v\ |\ I \vdash PI_v ] 
= \Pr_{I}[\mbox{one zero}]/\Pr_{I}[\mbox{at most one zero}] 
= {\ell+1 \over \ell + d} 
= {\ell+1 \over d}
= (\ell+1) \max_{p \in v} \Pr_{I}[ S(I) \vdash PS_p\ |\ I \vdash PI_p
]$. This is in line with \rcj{pf}. 

\medskip
\noindent {\bf Coverings:} 
Let $S_p$ be an $\ell$-rectangle if $S_p = \alpha \times
\Pi_{i \in [n]-i_p} D_i$, where $i_p \subset [n]$
specifies $\ell$ indexes and $\alpha \in \Pi_{i \in i_p} D_i$.  Say
that a set $\{S_p\}$ of $\ell$-rectangles covers maximally if each
$S_p$ covers some $I$ that the others do not. Let $U(r) =
\max_{\{S_p\ |\ p \in [r]\}} |\{I\ |\ I \not \in \cup_{p \in [r]} S_p
  \}$ be the maximum number of uncovered $I$. 

\cj{covering} 
$U(r) \le (1-d^{-\ell})^r d^n$, giving $U(r) \le q d^{n-\ell}$, when
$r = (\ell \ln d + \ln(1/q)) d^{\ell}$.
\ecj

\pfcj{covering} 
We want the $S_p$ to be different but overlap as much as possible.
This is done by having $i_p$ and $i_{p'}$ differ by at most one index.
This is what is done in the conjectured worse case.

Another option is to choose the $S_p$ randomly. First choose the $i_p$
using your favorite distribution and then choose $\alpha$ uniformly
at random. $(1-d^{-\ell})^r d^n$ is the expected number of uncovered
$I$.
\epf

\pfcj{pf} We will now use \rcj{covering} to prove a weaker version
\rcj{pf}.  Let $v$ be a node. Let $r = (\ell \ln d + \ln(1/q))
d^{\ell}$.  Let $\{S_p\ |\ p \in [r] \subset v\}$ be the first $r$
rectangles that cover maximally. Let $q = \max_{p \in v} \Pr_{I}[
S(I) \vdash PS_p\ |\ I \vdash PI_p ]$. The number of red balls in any
one $S_p$ is at most $q |S_p| = q d^{n-\ell}$. Hence, the number in
$\{S_p\ |\ p \in [r] \subset v\}$ is at most $r q d^{n-\ell}$. Lets
assume that all $I$ uncovered by $\{S_p\ |\ p \in [r] \subset v\}$ are
red. There are at most $U(r)$ of these. Hence, the total number of red
balls over all of $D^n$ is $r q d^{n-\ell} + U(r) \le (r+1) q
d^{n-\ell}$.  The number of $I$ covered by all $\{S_p\ |\ p \in v \}$
is at least $d^n - U(n) \approx d^n$. This gives that 
$\Pr_{I}[ S(I) \vdash PS_v\ |\ I \vdash
PI_v ] \le {\mbox{the number of red balls} \over d^n-U(n)} 
\le {r q d^{n-\ell} + U(r)  \over d^n-U(n)} 
\le {(r+1) q d^{n-\ell} \over d^n} 
= (\ell \ln d + \ln(1/q)) q$.
\epf

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Tree Width vs Parallel Width} \label{sec Parallel Width}

Allan was wondering about the power
of {\em tree width} verses that of {\em parallel width}.  The first is
the pFBT concept defined before, while the later imposes a restriction
that all of the branches start at the beginning of the computation
and survive until the end. Essentially, the computation consists of
$W$ independent parallel priority computations, resulting in the best
of these. We prove that there is a problem that can be done with tree
width $W\!=\!2$, but that requires parallel width $W = 2^{\Omega(n)}$. It
is analogous to many instances of a problem solved in serial being
able to reusing its bounded memory, while the memory requirements blow
up when the instances must be solved in parallel.

\begin{thm} \label{Parallel Width}
There is a problem that can be done with tree width $W\!=\!2$,
but that requires parallel width $W = 2^{\Omega(n)}$. 
\end{thm}

\begin{proof} of Theorem~\ref{Parallel Width} Let $P$ denote any computation problem that can
be solved with tree width $W\!=\!2$ but cannot be solved with width
$W\!=\!1$, even with lots of free data items. For example, the Bor
etal paper proves that width $W\!=\!2$ is needed to solve knapsack
with some competitive ratio. We could also scale down the
$2^{\Omega(\sqrt{n})}$ SAT result.  Let the constant $a$ be the
smallest number of data items needed in the input to obtain this
result. Let the constant $D = d^a$ be the total number of different
input instances to this problem. Let $P^{n \over a}$ denote the
problem consisting of $n \over a$ independent instances of $P$. The
input will consist of $n$ data items, $a$ for each of the $n \over a$
instances. Each data item will clearly say which of the $n \over a$
instances it is associated with. The task is to solve each of these $n
\over a$ instances to the required level of accuracy.

The problem can be solved with tree width $W\!=\!2$. The algorithm simply
solves the instances one at a time sequentially. After seeing the $a$
data items for the current instance, one of the two branches will
contain an valid solution for this instance. The other branch
dies. The computation continues on the living branch. In the end, the
final branch will contain an valid solution for each of the $n \over
a$ instances.

On the other hand, simple counting shows that any algorithm parallel
width $W$ that solves this problem requires $W \ge e^{n \over aD} =
2^{\Omega(n)}$.  Consider any branch of any such algorithm. Consider
how this branch solves the $i^{th}$ instance of $P$ for $i \in [{n
\over a}]$. This branch cannot solve this instance of $P$ for all $D$
input instance. This would contradict the fact that there is no
$W\!=\!1$ with algorithm for $P$. (Note the lower bound for $P$ needed
to allow for the algorithm to also receive dummy data items. See
Lemma~\ref{lm free data items}.)  To be nice, assume that it solves $P$ on $D\!-\!1$
of the instances. Similarly, this same branch solves $D\!-\!1$ of each
of the $n \over a$ instances. In order for this branch to solve the
instance of $P^{n \over a}$, it must solve each of the $n \over a$
instances of $P$. Hence, this branch solves at most $(D\!-\!1)^{n
\over a}$ instances of $P^{n \over a}$. However, there are $D^{n \over
a}$ instances of $P^{n \over a}$ to be solved. Hence, the number of
branches must be at least $W \ge [D^{n \over a}]/[(D\!-\!1)^{n \over
a}] \approx e^{n \over aD}$.

It is interesting that this reduction is almost tight.  Suppose that
for each of the $D$ possible instances to $P$, there is a $W\!=\!1$
width algorithm that fails to solve this instance but solves the
$D\!-\!1$ other instances. Choose an algorithm for $P^{n \over a}$ by
choosing independently for each of its $W$ branches and for each its
$n \over a$ instances of $P$ which of these $D$ algorithms for $P$ to
use.  Consider one of the $D^{n \over a}$ instances of $P^{n \over
a}$, one branch, and one $i \in [{n \over a}]$. The probability that
this branch solves the $i^{th}$ instances is ${D\!-\!1 \over D}$. The
probability that it solves each of the $n \over a$ instances is
$[{D\!-\!1 \over D}]^{n \over a} \approx e^{-{n \over aD}}$.  The
probability that each of the $W$ branches fails to solve this instance
of $P^{n \over a}$ is $[1-e^{-{n \over aD}}]^{n \over a}]^W \approx
e^{-(e^{-{n \over aD}})W}$. That this occurs for one of the $D^{n
\over a}$ instances is at most $e^{-(e^{-{n \over aD}})W} \cdot D^{n
\over a}$.  Setting $W > e^{n \over ad} \cdot {n \ln D \over a}$ gives
that this probability is strictly less than one. Hence, an algorithm
exists that solves each of these instances.

I have not been able yet, however, able to prove the lemma I first
wanted.  (Though it might now be of limited interest.) It is basically
the same question solved above, except the $P$ requires $w$ parallel
width and we want to know the parallel width requirement of $P^2$,
consisting of two independent copies of $P$. I conjecture that width
$W = \Omega(w^2)$ is needed. Consider the following problem of
covering a matrix with rectangle. The rows of the matrix are indexed
by instances of $P$ and the columns by instances of $P'$.  Each entry
of the matrix is an instance of $P \times P'$.  A single branch solves
the instances in a rectangle $S \times S'$ where $S$ are the instances
of $P$ solved and $S'$ the instances of $P'$. An algorithm for $P
\times P'$ with $W$ parallel width covers all the entries of the matrix
with $W$ such rectangles. Assuming that no $w$ of these rectangles can
cover all of the rows and no $w'$ of them can cover all of the
columns, prove that $\Omega(ww')$ rectangles are needed.




===


As seen in \rsec{sec free data items}, free data items can provide
extra power.  In addition to the $n$ data items one also receives $m$
free data items chosen from some large domain.  These have no bearing
on the solution of the problem and the algorithm need not make any
decision about them.  We show here that when the width is $W\!=\!1$,
the power of free data items is limited.  

\begin{lemma} \label{lm free data items}
When the width is only $W\!=\!1$, the free data items seems to be limited to increasing
$IP^{out}$ at only three times the speed that it is increased with out
them. \end{lemma}

This is not a proof.

The extra power comes as follows. The algorithm orders the data items
that remain possible. This ordering includes the possible free
items. The algorithm learns the first data item in this ordering that
is in the actual input instance. If this data item is a free item, the
algorithm still learns that all the possible data items that were
before it in the ordering are not in the input instance, i.e.\ are
added to $PI^{out}$. The scary thing is that this extra information
comes at no extra cost. But it is not so bad.  If the possible actual
data items and the free data items are distributed uniformly, then
${m+n \over n}$ is the expected number of free data items seen before
a real data item is seen. For each of these free data items, the
expected number of possible real data items added to $PI^{out}$ is
$q_i = {d_i \ln{W} \over m}$.  This number is given in the upper bound
Theorem~\ref{Thm: small d upper bound} and will be needed in the lower
bound. In total, the expected number of possible real data items added
to $PI^{out}$ is before a real data item is seen is then ${m+n \over
n} \times q_i \le {2 d_i \ln{W} \over n}$.  This is only a factor of
two away from the number added to $PI^{out}$ when a real data item is
seen. Hence, all is well.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Large Data Items} \label{large}

\bd
\i[Previous Model:] \mbox{}
\bd
\i[Contents of a Data Item:] Suppose at first that the computational
problem's input is a graph $G$ and that decision are made about its
edges $e$ (or its nodes $v$). The most natural way to represent the
input would be to have one data item for each edge containing the
names of the two adjacent nodes and the weight of the edge. Sometimes,
however, to have an efficient algorithm, the degrees of these nodes
is needed and maybe even their adjacency lists. Even though
decisions are being made about the edges, another option is to have a
data item for each node containing its adjacency list. One concern
about the priority model is that the complexity of a problem can
depend a great deal on such representation details. What is clear,
however, is that the more information included, the better off the
algorithm is.

\i[The Decisions Made:] If each data item contains a node and its
adjacency list and decisions need to be made about the edges, then the
standard thing to do is to require the algorithm to make an
irrevocable decision about each of the edges seen. It would be more
generous to the algorithm to only require it to make a decision at
this time about one specific edge.
\ed

\i[The New Model:] \mbox{}
\bd
\i[The Broad Local Priority and BT Model:] 
Our idea is to include in each data item as much local information
about an object as the algorithm wants before it is forced into an
irrevocable decision about it and then to require it to make a
decision about only this one object at this time.

The parameter $q$ will specify the amount of information accessible to
the algorithm. For each object $e$, let $G_e$ be the sub-graph
containing all edges of $G$ that are reachable from $e$ by paths of
length $\ell_e$, where $\ell_e$ is chosen dynamically so that $G_e$
contains approximately $q$ edges. The data item for the edge $e$ will
specify all of $G_e$. When a priority or BT algorithm sorts the edges
it can do so using all of this information. When it receives the next
edge $e$, it receives all of this information. Then using this
information, it must make an irrevocable decision about $e$. It can
delay making decisions about the remaining edges in $G_e$ until it
receives the data items associated with these edges.

\i[3-SAT:] The same ideas can be used for any input type as long as there
is a sense of the locality the objects. 3-SAT, for example, has a
set of clauses as inputs. The standard BT model has a data item for
each variable and to include in this data item a full description of
all clauses that the variable is in. Our model, on input $\I$, defines
a graph on the variables with an edge between two variables if they
share a clause. It stores $\I_x$ in the data item associated with
variable $x$, where $\I_x$ contains the full description of every
clause containing a variable that is reachable in this graph from $x$
by a path of length $\ell_x$, where $\ell_x$ is chosen dynamically so
that $\I_x$ contains approximately $q$ variables.

\i[BT Width:] Borodin et al defines the width $w$ of a BT computation to
be the width of the tree of decisions or equivalently the number of
decision vectors that can be simultaneously kept.

\ed
\ed

\begin{thm} \label{any}
``Any'' computation problem with data item
size $q$ can be solved optimally with decision tree width $w=
2^{\bigO(n/q)}$.
\end{thm}

\begin{thm} \label{3sat} 3-SAT with data item size $q$ requires tree width $w=
2^{\Omega(n/q)}$. 
\end{thm}

\begin{proof} of Theorem~\ref{any} We prove that any computation problem with data item size
$q$ can be solved optimally with decision tree width $w=
2^{\bigO(n/q)}$.

Each data items reveals $q$ of the $n$ objects in the input instance.
The algorithm greedily ask for a data item that gives as much as
possible of the input not seen before. (**Not Proved**) After
$\bigO({n\over q})$ data items, the algorithm has seen the entire
input. Hence, with its unbounded computation power, it knows the
optimal solution. As it sees the $\bigO({n\over q})$ data items, the
algorithm builds a tree of width $w= 2^{\bigO(n/q)}$ considering every
possible answer for these. The optimal solution will be an extension
of one of these partial solutions.
\end{proof}


\begin{proof} of Theorem~\ref{3sat} 
By way of contradiction, suppose there is an
algorithm with data item size $q$ that can solve 3-SAT with decision
tree width $w= 2^{\Omega(n'/q)}$, where $n'$ is the number of
variables.

The proof is a reduction to 3-SAT in the model where each data item
contains a variable and a full description of all the clauses that the
variable is in. Consider an input instance $\I$ with $n$ variables and
$m$ 3-clauses. We map it to an input instance $\I'$ with $n' = 6qm$
variables as follows. Start by building a graph with a node $u_x$ for
each variable $x$ in $\I$. Node $u_x$ will be the center of a star of
paths fanning out. For each clause $c$ containing $x$, there will be
a path $u_x = v_{\left<x,c,1\right>}, \ldots, v_{\left<x,c,2q\right>}$
of length $2q$. The instance $\I'$ will have a variable for each node
in this graph. For each edge $\left\{v_{\left<x,c,i\right>},
v_{\left<x,c,i+1\right>}\right\}$, there will be two clauses $\neg
v_{\left<x,c,i\right>} \wedge v_{\left<x,c,i+1\right>}$ and
$v_{\left<x,c,i\right>} \wedge \neg v_{\left<x,c,i+1\right>}$. Note
that for both of these clause to be satisfied, these two variable must
be given the same values. Following this logic along the paths, all
the variables in the star associated with a variable $x$ must all have
the same value. To conclude the construction, the instance $\I'$ will
have the original clauses $c$, but instead of using the original
variable $x$, it will use the new variables
$v_{\left<x,c,2q\right>}$. In the graph, this puts a clique between
the nodes $v_{\left<x,c,2q\right>}$, $v_{\left<y,c,2q\right>}$, and
$v_{\left<z,c,2q\right>}$, when $c$ contains the three variables $x$,
$y$, and $z$.

The rest of the reduction is identical to Nassim wrote up. The each
of our data items, being associated with a variable $x$, is mapped to
the entire star of variables $v_{\left<x,c,i\right>}$. When the
mirrored algorithm receives all clauses within distance $q$ from
$v_{\left<x,c,i\right>}$, it learns no more than we learn, namely a
full description of the clauses that $x$ is in. We set $x$ the same
that it sets $v_{\left<x,c,i\right>}$. We do not need to worry about
``free branches'' because when their algorithm later sets
$v_{\left<x,c,i'\right>}$, we only need to follow one of their branches.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}



