text:
\section{Introduction}

The idea of \emph{knowledge compilation}
is to deal with the intractability
of certain computational tasks
on a knowledge base by compiling it
into a different data structure
where the tasks are feasible.
The choice of the target data structure
involves an unavoidable trade-off between succinctness and tractability.

Darwiche and Marquis \cite{DarwicheM02} systematically investigated
this trade-off in the fundamental case where the knowledge bases are boolean functions
and the data structures are classes of boolean circuits (\emph{representation languages}).

In their setting, \emph{decomposable negation normal forms (DNNFs)}
and \emph{ordered binary decision diagrams (OBDDs)}
arise as benchmark
languages for succinctness and tractability respectively \cite{Darwiche01,DarwicheM02}.
On the one hand, DNNFs are exponentially more succinct than OBDDs;
moreover, in contrast to OBDDs, they implement efficiently conjunctive normal forms
of small treewidth \cite{Darwiche01,RazgonP13,OztokD14,Razgon14}.  On the other hand,
the vast applicability of OBDDs in verification and synthesis
relies on the tractability of equivalence testing (speeded up by canonicity)
and boolean combinations, which DNNFs lack \cite{DarwicheM02}.

This gap between DNNFs (succinct but hard) and OBDDs (verbose but tractable)
led to the quest for intermediate languages
exponentially more succinct than,
but essentially as tractable as, OBDDs.

Introduced by Darwiche \cite{Darwiche11},
\emph{sentential decision diagrams (SDDs)}
are a most prominent candidate
to narrow the gap between DNNFs and OBDDs.  They are designed
by strengthening the decomposability property \cite{PipatsrisawatD08}
and further imposing a very strong form of determinism \cite{PipatsrisawatD10}.  The resulting language
can implement decisions of the form
\begin{equation}\label{eq:sent-dec-intro}
\bigvee_{i=1}^m P_i(X) \wedge S_i(Y)\text{,}
\end{equation}
where $X$ and $Y$ are disjoint sets of variables nicely structured by an underlying
\emph{variable tree},
and the subcircuits $P_1,\ldots,P_m$, called \emph{primes},\footnote{The $S_i$'s are called \emph{subs}.} implement an exhaustive case distinction
into exclusive and consistent cases.\footnote{Formally,
the models of $P_1,\ldots,P_m$ partition the set of assignments of $X$ to $\{0,1\}$ into $m$ nonempty blocks; see Section~\ref{sect:back}.}
Binary (or Shannon) decisions in OBDDs boil down to very special sentential decisions having the form
$$(\neg x \wedge S_1(Y)) \vee (x \wedge S_2(Y))\text{,}$$
where the variable $x$ is not in the variable set $Y$.

Indeed, SDDs properly contain OBDDs,
and hence are at least as succinct as OBDDs,
while preserving tractability of all key tasks that are tractable on OBDDs.
For this reason, they have been used in a variety
of applications in artificial intelligence and probabilistic reasoning,
as reported, for instance, by \cite{BroeckDarwiche15,OztokDarwiche15}.

Not only SDDs are as tractable as OBDDs,
but they also tend to be more succinct than OBDDs in practice;
in fact, knowledge compilers often produce much smaller SDDs than OBDDs by heuristically
leveraging the additional flexibility of variable trees in SDDs
with respect to variable orderings in OBDDs \cite{ChoiD13,OztokDarwiche15}.

Nonetheless,
the basic theoretical question about the relative succinctness of OBDDs and SDDs
has been open since Darwiche introduced SDDs \cite{Darwiche11,Razgon13}:
\begin{quote}
\textit{Are SDDs exponentially more succinct than OBDDs?}
\end{quote}
The results in the literature did not even exclude the possibility for OBDDs to polynomially simulate SDDs \cite{XueCD12},
until recently Razgon proved a quasipolynomial separation \cite{Razgon13}.  The above question stands,
though, as for instance OBDDs could still quasipolynomially simulate SDDs.

\paragraph{Contribution.}   We prove in this article that
SDDs are exponentially more succinct than OBDDs.  Thus, in particular,
OBDDs cannot quasipolynomially simulate SDDs.

More precisely,
\emph{we construct an infinite family of boolean functions such that
every member of the family
has polynomial compressed SDD size but exponential OBDD size} (Theorem~\ref{th:exp-sep})

\emph{Compressed} SDDs contain OBDDs,\footnote{More precisely, compressed SDDs contain reduced OBDDs;
see \cite[Definition~1.3.2]{Wegener00}.} and are regarded as a natural SDD class because of their \emph{canonicity}: two compressed SDDs computing the same function
are syntactically equal up to syntactic manipulations preserving polynomial size \cite{Darwiche11}.
The restriction to compressed SDDs makes our result stronger,
because general SDDs are believed (despite not known) to be exponentially more succinct than compressed SDDs \cite{BroeckDarwiche15}.

We separate compressed SDDs and OBDDs by a function,
which we call the \emph{generalized hidden weighted bit} function because,
indeed, it contains the \emph{hidden weighted bit} function (HWB) as a subfunction.
HWB is perhaps the simplest function known to be hard on OBDDs \cite{Bryant86}:
it computes the subsets of $\{1,\ldots,n\}$
having size $i$ and containing the number $i$,
for $i=1,\ldots,n$.

It turns out that HWB itself has small (uncompressed) SDDs (Theorem~\ref{th:sdd-size}),
which immediately separates SDDs and OBDDs.  The construction,
a slight variation of which gives the compressed case (Lemma~\ref{lemma:sdd-size} and Lemma~\ref{lemma:obdd-size}),
is based on the following two observations.

The first observation is that HWB
can be expressed
as a sentential decision of the form (\ref{eq:sent-dec-intro}) by distinguishing the following primes:
\begin{itemize}
\item for $i=1,\ldots,n$, the subsets of size $i$ containing the number $i$
(each of these $n$ primes is taken by HWB, so their subs will be equivalent to $\top$);
\item the empty subset,
and the subsets of size $i$ not containing the number $i$ for $i=1,\ldots,n-1$ (none of these $n$ primes is taken by HWB,
so their subs will be equivalent to $\bot$).
\end{itemize}
The second observation is that each of the above primes has small OBDD size under any variable ordering (Proposition~\ref{prop:obdd-pi}).  With these two observations
it is fairly straightforward to implement the hidden weighted bit function
by a small (uncompressed) SDD (Theorem~\ref{th:sdd-size}).

A direct inspection of our construction allows to straightforwardly derive
some facts about compression previously observed in the literature \cite{BroeckDarwiche15},
namely that the SDD size may increase exponentially either by compressing SDDs over fixed variable trees,
or by conditioning (unboundedly many variables) over fixed variable trees (see Section~\ref{sect:disc}).

\paragraph{Organization.} The article is organized as follows.  In Section~\ref{sect:back}
we present the technical background,
culminating in the quasipolynomial separation of SDDs and OBDDs proved by Razgon
(Theorem~\ref{th:raz}). In Section~\ref{sect:main},
we separate (uncompressed) SDDs and OBDDs by the hidden weighted bit function (Theorem~\ref{th:sdd-size})
and then modify the construction to separate compressed SDDs and OBDDs (Theorem~\ref{th:exp-sep}).
We discuss our results in Section~\ref{sect:disc}.

\section{Background}\label{sect:back}

We collect background notions and facts from the literature \cite{DarwicheM02,PipatsrisawatD08,Darwiche11,Razgon13}.

\paragraph{Structured Deterministic NNFs.}
Let $X$ be a finite set of variables.
Let $C$ be a boolean circuit on input variables $X$,
built using fanin $0$ constant gates (labelled by $\bot$ or $\top$),
fanin $1$ negation gates (labelled by $\neg$),
and unbounded fanin disjunction and conjunction gates (labelled by $\vee$ and $\wedge$).
The unique sink node (outdegree $0$)
in the underlying directed acyclic graph (DAG) of $C$
is called the output gate of $C$;
source nodes (indegree $0$) are called input gates,
and are labelled by constants or variables in $X$; in particular,
$C$ is allowed to not read some of the variables in $X$, see Figure~\ref{fig:struct} (left).

A boolean circuit $C$ on variables $X$ is in \emph{negation normal form}, in short an \emph{NNF},
if the gates labelled by $\neg$ have wires only from input gates.  Without loss of generality
we assume that NNFs have input gates labelled by constants or literals on variables in $X$
(and no internal gates labelled by $\neg$).

As usual, an NNF $C$ on input variables $X$ computes a boolean function $f \colon \{0,1\}^X \to \{0,1\}$;
in this case we also write $C \equiv f$.  Two NNFs $C$ and $C'$ on the same input variables are equivalent
if they compute the same boolean function; again we write $C \equiv C'$.

The \emph{size} of an NNF $C$, in symbols $\mathrm{size}(C)$,
is the number of arcs in its underlying DAG.
Let $f$ be a boolean function
and let $\mathcal{L}$ be a class of NNFs.
The \emph{size of $f$ relative to $\mathcal{L}$}
(or, in short, the \emph{$\mathcal{L}$ size of $f$}),
denoted by $\mathcal{L}(f)$,
is equal to the minimum over the sizes of all circuits in $\mathcal{L}$ computing $f$:
$$\mathcal{L}(f)=\mathrm{min}\{ \mathrm{size}(C) \colon C \in \mathcal{L}, C \equiv f\}\text{.}$$

Let $C$ be an NNF on input variables $X$,
and let $g$ be a gate of $C$.
We denote by $C_{g}$ the subcircuit of $C$ having $g$ as its output gate,
that is, the circuit whose underlying DAG is
the subgraph of the underlying DAG of $C$
induced by the nodes having a directed path to $g$ (labelled as in $C$).

\smallskip

An NNF $C$ on input variables $X$ is \emph{deterministic}
if, for every $\vee$-gate $g$ in $C$, say of the form $\bigvee_{i=1}^m g_i$,
it holds that $$C_{g_i} \wedge C_{g_j} \equiv \bot$$ for all $1 \leq i < j \leq m$,
where we formally regard $C_{g_i}$, $C_{g_j}$, and $\bot$ as NNFs on input variables $X$.
We denote by $\mathcal{NNF}_d$ the class of all deterministic NNFs.

\smallskip

Let $Y$ be a finite nonempty set of variables.
A \emph{variable tree} (in short, a \emph{vtree}) for the variable set $Y$ is a
rooted, full, ordered, binary tree $T$
whose leaves correspond bijectively to $Y$; indeed,
we identify each leaf in $T$ with the variable in $Y$ it corresponds to.

Let $v$ be an internal node of the vtree $T$.  We let
$v_l$ and $v_r$ denote respectively the left and right child of $v$,
and $T_{v}$ denote the subtree of $T$ rooted at $v$.
We also let $Y_v \subseteq Y$ denote (the variables corresponding to) the leaves
of $T_v$; clearly $T_v$ is a vtree for the variable set $Y_v$.

\smallskip

Let $C$ be an NNF on input variables $X$,
and let $T$ be a vtree for the variable set $Y$.

We say that $C$ \emph{respects $T$} if the following holds.
First, every $\wedge$-gate $g$ in $C$ has fanin exactly $2$.
Second, let $g$ be an $\wedge$-gate in $C$ having wires from gates $h_1$ and $h_2$.
Then there exists an internal node $v$ in $T$ such that
the input gates of the subcircuit $C_{h_1}$
mention only variables in $T_{v_l}$
and the input gates of the subcircuit $C_{h_2}$
mention only variables in $T_{v_r}$.  In this case, we also say that $g$ respects $v$.

Note that, in particular,
the sets of variables mentioned by $C_{h_1}$
and $C_{h_2}$ are disjoint; it follows that $C$ is decomposable \cite{Darwiche01}.
Also note that, by definition, if an NNF reading all the variables in a set $X$
is structured by a vtree for the variable set $Y$,
then $X \subseteq Y$ and the inclusion can be strict;
see Figure~\ref{fig:struct}.  This feature is crucial in our construction
(see, for instance, the proof of Theorem~\ref{th:sdd-size}).

A \emph{structured NNF} is an NNF respecting some vtree.  See Figure~\ref{fig:struct}.
We denote by $\mathcal{NNF}_s$ the class of all structured NNFs.

\begin{figure}[t!]
\centering
\begin{picture}(0,0)%
\includegraphics{example1_pspdftex}%
\end{picture}%
\setlength{\unitlength}{2901sp}%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(4111,2018)(8858,-429)
\put(9805,344){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_2$}%
}}}}
\put(12323,1019){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$y$}%
}}}}
\put(11830,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_3$}%
}}}}
\put(9384,793){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\wedge$}%
}}}}
\put(8922,333){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bot$}%
}}}}
\put(10930,569){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_1$}%
}}}}
\put(11380,119){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_2$}%
}}}}
\put(12730,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\end{picture}%
\caption{A circuit on input variables $\{x_2,x_4\}$ on the left (in the underlying DAG,
the edges are oriented upwards), respecting the vtree for the variable set $\{x_1,x_2,x_3,x_4,y\}$ on the right.
The left subtree is a vtree for the variable set $\{x_1,x_2,x_3,x_4\}$,
and the right subtree is a vtree for the variable set $\{y\}$.
The $\wedge$-gate in the circuit respects the root of the vtree.}
\label{fig:struct}
\end{figure}

\paragraph{SDDs and OBDDs.}
A \emph{sentential decision diagram (SDD) $C$ respecting a vtree $T$}
is defined inductively as follows.
\begin{itemize}
\item $C$ is a single gate labelled by a literal on a variable $x$,
and $x$ is in the variable set of $T$.
\item $C$ is a single gate labelled by a constant, and $T$ is any vtree.
\item $C$ is formed by an output gate $g$ labelled by $\vee$,
with $m \geq 2$ wires from gates $g_1,\ldots,g_m$ labelled by $\wedge$,
where each $g_i$ has wires from two gates $p_i$ and $s_i$, that is,
\begin{equation}\label{eq:or-node}
C=\bigvee_{i=1}^m C_{p_i} \wedge C_{s_i}\text{,}
\end{equation}
such that for some internal node $v$ of $T$ the following holds ($i=1,\ldots,m$):
\begin{description}
\item[{\bf(S1)}] $C_{p_i}$ is an SDD respecting a subtree of $T_{v_l}$
\item[{\bf(S2)}]  $C_{s_i}$ is an SDD respecting a subtree of $T_{v_r}$.
\item[{\bf(S3)}] $C_{p_i} \not\equiv \bot$.
\item[{\bf(S4)}] $C_{p_i} \wedge C_{p_j} \equiv \bot$ ($1 \leq i<j \leq m$).
\item[{\bf(S5)}] $\bigvee_{i=1}^m C_{p_i} \equiv \top$.
\end{description}
\end{itemize}
In the equivalences in (S3)-(S5), we formally regard the $C_{p_i}$'s, $\bot$ and $\top$
as NNFs on variables $Y_{v_l}$.  In words, conditions (S3)-(S5) say that
the $C_{p_i}$'s define a partition of $\{0,1\}^{Y_{v_l}}$
into $m$ nonempty blocks, where the $i$th block contains exactly
the models of $C_{p_i}$ ($i=1,\ldots,m$).

An SDD is an SDD respecting some vtree.  We let $\mathcal{SDD}$
denote the class of all SDDs.

An SDD $C$ is called \emph{compressed} if the following holds.
Let $h$ be an $\vee$-gate of $C$,
so that $h=\bigvee_{i=1}^{m'} C_{p'_i} \wedge C_{s'_i}$ specified as in
(\ref{eq:or-node}) relative to some node $v'$ in $T$. Then
\begin{description}
\item[{\bf(C)}] $C_{s'_i} \not\equiv C_{s'_j}$ ($1 \leq i<j \leq m'$),
\end{description}
where we formally regard $C_{s'_i}$ as an NNF on variables $Y_{v'_r}$ for $i=1,\ldots,m'$.
We let $\mathcal{SDD}_c$ denote the class of all compressed SDDs.

\smallski
An \emph{ordered binary decision diagram (OBDD)} is a compressed SDD
respecting a \emph{right-linear} vtree $T$ (that is,
where each left child is a leaf); see Figure~\ref{fig:right-linear-tree}.
We let $\mathcal{OBDD}$ denote the class of all OBDDs.\footnote{Reduced OBDDs as usually defined in the literature \cite[Definition~1.3.2]{Wegener00}
are indeed compressed SDD respecting right-linear vtrees \cite[Section~6]{Darwiche11}.}

\begin{figure}[t!]
\centering
\begin{picture}(0,0)%
\includegraphics{example2_pspdftex}%
\end{picture}%
\setlength{\unitlength}{2901sp}%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(2086,1568)(10883,-429)
\put(11830,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_3$}%
}}}}
\put(10930,569){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_1$}%
}}}}
\put(11380,119){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_2$}%
}}}}
\put(12730,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\end{picture}%

\caption{A right-linear vtree; its left first traversal induces the variable ordering $x_1<x_2<x_3<x_4$.}
\label{fig:right-linear-tree}
\end{figure}

Let $C$ be an OBDD respecting a vtree $T$,
and let $\sigma=x_1<\cdots<x_n$ be the variable ordering
induced by a left first traversal of $T$; in this case,
we also say that $C$ respects $\sigma$.
For an ordering $\sigma$ of a set of variables,
we let $\mathcal{OBDD}_\sigma$ denote the class of all OBDDs respecting $\sigma$.

\paragraph{Quasipolynomial Separation.} It follows from the definitions that
\begin{equation}\label{eq:inclusions}
\mathcal{OBDD} \subseteq \mathcal{SDD}_c \subseteq \mathcal{SDD} \subseteq \mathcal{NNF}_{s} \cap \mathcal{NNF}_{d}\text{}
\end{equation}
which raises the natural question how OBDDs and SDDs
are related in succinctness; indeed, the quest for the relative succinctness of
OBDDs and SDDs has been an open problem in knowledge compilation since
Darwiche introduced SDDs \cite{Darwiche11}.

Recently, Razgon \cite[Corollary~3]{Razgon13} has
established a \emph{quasipolynomial separation} of OBDDs from compressed SDDs

\begin{theorem}[Razgon]\label{th:raz}
There exists an unbounded arity class of boolean functions $\mathcal{F}$
such that every arity $n$ function $f \in \mathcal{F}$ has $\mathcal{SDD}_c$ size in $O(n^3)$
and $\mathcal{OBDD}$ size in $n^{\Omega(\log n)}$.
\end{theorem}

We remark that the restriction to compressed SDDs in the above statement is nontrivial;
to the best of our knowledge, compressed SDDs
might be exponentially more succinct than uncompressed SDDs \cite{BroeckDarwiche15};
see also the discussion in Section~\ref{sect:disc}.

\section{Exponential Separation}\label{sect:main}

The quasipolynomial separation stated in Theorem~\ref{th:raz}
implies that OBDDs do not simulate SDDs in polynomial size,
but leaves open the possibility for OBDDs to simulate SDDs in quasipolynomial size.
In this section
we exclude this possibility by establishing
an \emph{exponential separation}
of OBDDs from compressed SDDs

\paragraph{Hidden Weighted Bit.} The separation is obtained by (a variant of) the \emph{hidden weighted bit} function
$$\mathrm{HWB}_n(x_1,\ldots,x_n)\text{,}$$
that is the boolean function on $n$ inputs $x_1,\ldots,x_n$ such that,
for all assignments $f \colon \{x_1,\ldots,x_n\} \to \{0,1\}$,
it holds that $f$ is a model of $\mathrm{HWB}_n$ if and only if $f(x_1)+\cdots+f(x_n)=i$
and $f(x_i)=1$ ($i \geq 1$).

It is well known that the hidden weighted bit function has exponential OBDD size \cite{Bryant86}.

\begin{theorem}[Bryant]\label{th:bryant}
The $\mathcal{OBDD}$ size of $\mathrm{HWB}_n$ is $2^{\Omega(n)}$.
\end{theorem}

Intuitively, a model of $\mathrm{HWB}_n$ is a subsets of $\{1,\ldots,n\}$
of size $i$ containing the number $i$, for $i=1,\ldots,n$.  For instance,
$\mathrm{HWB}_2(1,0)=1$, because the set $\{1\}$ has size $1$ and contains the number $1$,
and $\mathrm{HWB}_2(0,1)=0$, because the set $\{2\}$ has size $1$ but does not contain the number $1$.

The simple but crucial observation underlying our construction is
that the models of $\mathrm{HWB}_n$ can be decided arguing by cases, as follows:
If $S$ is a subset of $\{1,\ldots,n\}$ of size $i$,
then $S$ is a model of $\mathrm{HWB}_n$ if and only if $i \in S$ ($i=1,\ldots,n$).
With this insight it is not hard to setup an exhaustive and exclusive
case distinction equivalent to $\mathrm{HWB}_n$;
the key observation is that each individual case in the distinction
is computable by a small OBDD with respect to any variable ordering.

We formalize the above intuition.  For $i \in \{0,1,\ldots,n\}$,
let $$E^i_n(x_1,\ldots,x_n)$$ be the boolean function
on $n$ inputs $x_1,\ldots,x_n$ such that,
for all assignments $f \colon \{x_1,\ldots,x_n\} \to \{0,1\}$,
it holds that $f$ is a model of $E^i_n$ if and only if $f(x_1)+\cdots+f(x_n)=i$. Hence
$E^i_n$ computes the subsets of $\{1,\ldots,n\}$
of size $i$ ($i \geq 0$).  Let now
\begin{equation}\label{eq:family-P}
\mathcal{P}_n=\{P_0,P_n\} \cup \{P_{i,0},P_{i,1} \colon i=1,\ldots,n-1\}
\end{equation}
be the family of $2n$ boolean functions, each over the variables $\{x_1,\ldots,x_n\}$,
defined as follows:
\begin{itemize}
\item $P_{0} \equiv E^0_n$
\item $P_{n} \equiv E^n_n$
\end{itemize}
and for $i=1,\ldots,n-1$ let
\begin{itemize}
\item $P_{i,0} \equiv E^i_n \wedge \neg x_i$
\item $P_{i,1} \equiv E^i_n \wedge x_i$
\end{itemize}
See Figure~\ref{fig:ein-proj} for an illustration.

Each function in $\mathcal{P}_n$ computes a family of subsets of $\{1,\ldots,n\}$.
Namely, $P_0$ computes the empty subset,
$P_n$ computes $\{1,\ldots,n\}$,
$P_{i,0}$ computes the subsets of $\{1,\ldots,n\}$ of size $i$ not containing the number $i$,
and $P_{i,1}$ computes the subsets of $\{1,\ldots,n\}$ of size $i$ containing the number $i$ ($i=1,\ldots,n-1$).

It is readily observed that the members of
$\mathcal{P}_n$ partition the powerset of $\{1,\ldots,n\}$ in nonempty blocks.
Formally,

\begin{fact}\label{fact:part}
Let $\mathcal{P}_n$ be as in (\ref{eq:family-P}),
and let $P,P' \in \mathcal{P}_n$ with $P \neq P'$.
\begin{itemize}
\item $P \not\equiv \bot$.
\item $P \wedge P' \equiv \bot$.
\item $\bigvee_{P \in \mathcal{P}_n}P \equiv \top$.
\end{itemize}
\end{fact}

We now establish the key property,
that each member of $\mathcal{P}_n$ is computable by a small OBDD
with respect to any variable ordering.

First consider the functions $E^i_n$.  An OBDD computing $E^i_n$ with respect to the variable ordering $\sigma=x_1<\cdots<x_n$
is displayed in Figure~\ref{fig:ein-obdd} for the case $n=4$ and $i=2$.  Generalizing the construction,
we have that an OBDD $C$ computing $E^i_n$ and respecting $\sigma$
has at most $1+2+\cdots+n=n(n+1)/2$ decision nodes,
each contributing $6$ wires in the circuit; hence $C$ has size $O(n^2)$.

Since $E^i_n$ is symmetric \cite[Definition~2.3.2 and Lemma~4.7.1]{Wegener00}, the following holds.

\begin{proposition}\label{prop:obdd-ein}
Let $\sigma$ be an ordering of $x_1,\ldots,x_n$.
The $\mathcal{OBDD}_\sigma$ size of $E^i_n$ is $O(n^2)$.
\end{proposition}

\begin{figure}[t!]
\centering
\begin{picture}(0,0)%
\includegraphics{ein-obdd_pspdftex}%
\end{picture}%
\setlength{\unitlength}{2901sp}%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(3886,2086)(9533,-879)
\put(11380,1019){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_1$}%
}}}}
\put(10930,569){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_2$}%
}}}}
\put(11830,569){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_2$}%
}}}}
\put(11380,119){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_3$}%
}}}}
\put(10480,119){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_3$}%
}}}}
\put(12280,119){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_3$}%
}}}}
\put(12730,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\put(10030,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\put(9600,-789){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bot$}%
}}}}
\put(12300,-789){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bot$}%
}}}}
\put(13200,-789){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bot$}%
}}}}
\put(10930,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\put(11830,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\put(10500,-789){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bot$}%
}}}}
\put(11400,-800){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\top$}%
}}}}
\put(10750,-288){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v$}%
}}}}
\end{picture}%

\caption{An OBDD for the boolean function $E^2_4$ respecting the variable ordering $x_1<x_2<x_3<x_4$,
drawn (in an unreduced form) using the graphical conventions for decision diagrams \cite{Wegener00}.  Each decision node generates $6$ wires in the circuit;
for instance, the decision node $v$ generates a $6$-wire subcircuit isomorphic to $(\neg x_4 \wedge \bot) \vee (x_4 \wedge \top)$.}
\label{fig:ein-obdd}
\end{figure}

It follows that every $P \in \mathcal{P}_n$ has a small OBDD
with respect to every variable ordering.

\begin{proposition}\label{prop:obdd-pi}
Let $\sigma$ be an ordering of $x_1,\ldots,x_n$ and let $P \in \mathcal{P}_n$, where $\mathcal{P}_n$ is as in (\ref{eq:family-P}).
The $\mathcal{OBDD}_\sigma$ size of $P$ is $O(n^2)$.
\end{proposition}
\begin{proof}
For $P_0$ and $P_n$ the statement follows directly from Proposition~\ref{prop:obdd-ein}.
For $i=1,\ldots,n-1$ we have that $P_{i,0} \equiv E^i_n \wedge \neg x_i$
and $P_{i,1} \equiv E^i_n \wedge x_i$.

Recall that if $f$ and $f'$ are boolean functions on $X$,
and $\rho$ is any ordering of $X$, then \cite[Theorem~3.3.6]{Wegener00}:
\begin{equation}\label{eq:conj-quadr}
\mathcal{OBDD}_{\rho}(f \wedge f') \leq \mathcal{OBDD}_{\rho}(f) \cdot \mathcal{OBDD}_{\rho}(f')\text{.}
\end{equation}

Regarding the literals $\neg x_i$
and $x_i$ as boolean functions on $\{x_1,\ldots,x_n\}$ whose $\mathcal{OBDD}_\sigma$ size
is constant ($6$ wires),
the statement follows from (\ref{eq:conj-quadr}) and Proposition~\ref{prop:obdd-ein}.
\end{proof}

\begin{figure}[t!]
\centering
\begin{picture}(0,0)%
\includegraphics{ein-proj_pspdftex}%
\end{picture}%
\setlength{\unitlength}{2901sp}%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(2986,2086)(9533,-879)
\put(11380,1019){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_1$}%
}}}}
\put(10930,569){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_2$}%
}}}}
\put(11830,569){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_2$}%
}}}}
\put(11380,119){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_3$}%
}}}}
\put(10480,119){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_3$}%
}}}}
\put(10030,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\put(9600,-789){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bot$}%
}}}}
\put(12300,-789){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bot$}%
}}}}
\put(12300,111){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bot$}%
}}}}
\put(10930,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\put(11830,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\put(10500,-789){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\bot$}%
}}}}
\put(11400,-800){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\top$}%
}}}}
\end{picture}%

\caption{An OBDD for the boolean function $E^2_4 \wedge \neg x_2$ respecting the variable ordering $x_1<x_2<x_3<x_4$.}
\label{fig:ein-proj}
\end{figure}

\paragraph{SDDs vs OBDDs.}  We now prove that the hidden weighted bit function
has small (uncompressed) SDD size;
a slight modification of the construction, described later,
gives the compressed case.

The key observation is that, by the definition of $\mathcal{P}_n$,
the hidden weighted bit function $\mathrm{HWB}_n$
is equivalent to
\begin{equation}\label{eq:sdd-hwb-form}
(P_0 \wedge \bot) \vee (P_n \wedge \top) \vee \bigvee_{i=1}^{n-1} ((P_{i,0} \wedge \bot) \vee (P_{i,1} \wedge \top))\text{}
\end{equation}
because the latter is equivalent to
$$(E^1_n \wedge x_1) \vee \cdots \vee (E^n_n \wedge x_n)$$
which is in turn equivalent to $\mathrm{HWB}_n$.
Using the form (\ref{eq:sdd-hwb-form}), it is easy to build an SDD
computing $\mathrm{HWB}_n$ and respecting a vtree for $\{x_1,\ldots,x_n,y\}$
like the one on the right in Figure~\ref{fig:struct};
upon implementing the $P_i$'s and $P_{i,j}$'s by OBDDs,
the construction has polynomial size by Proposition~\ref{prop:obdd-pi}.  Note that the SDD is not compressed
because $\bot$ and $\top$ are reused $n$ times. The details follow.

\begin{theorem}\label{th:sdd-size}
The $\mathcal{SDD}$ size of $\mathrm{HWB}_n$ is $O(n^3)$.
\end{theorem}
\begin{proof}
We first define an NNF $C$ on input variables $X=\{x_1,\ldots,x_n\}$ computing (\ref{eq:sdd-hwb-form})
as follows.  The output gate of $C$ is a fanin $2n$ $\vee$-gate,
with wires from $2n$ fanin $2$ $\wedge$-gates $g_0$, $g_n$, and $g_{i,j}$ for $i=1,\ldots,n-1$ and $j=0,1$.

Let $p_0$ and $s_0$ be the two gates wiring $g_0$,
let $p_n$ and $s_n$ be the two gates wiring $g_n$,
and for $i=1,\ldots,n-1$ and $j=0,1$ let $p_{i,j}$ and $s_{i,j}$ be the two gates wiring $g_{i,j}$.

Let $\sigma$ be any ordering of $x_1,\ldots,x_n$.  All the subcircuits of $C$
rooted at $p_0$, $s_0$, $p_n$, $s_n$, $p_{i,j}$, and $s_{i,j}$
($i=1,\ldots,n-1$, $j=0,1$) are OBDDs respecting the ordering $\sigma$.  Moreover:
\begin{itemize}
\item $C_{p_i}$ computes $P_i$ for $i \in \{1,n\}$;
\item $C_{p_{i,j}}$ computes $P_{i,j}$ for $i=1,\ldots,n-1$, $j=0,1$;
\item $C_{s_0}$ and $C_{s_{i,0}}$ compute $\bot$ for $i=1,\ldots,n-1$;
\item $C_{s_n}$ and $C_{s_{i,1}}$ compute $\top$ for $i=1,\ldots,n-1$.
\end{itemize}

We prove that $C$ is an SDD respecting a suitable vtree $T$
for the variable set $X \cup \{y\}$.  Roughly, $T$ is
a right-linear vtree with the exception of the variable $y$;
see the diagram on the right in Figure~\ref{fig:struct} for the case $n=4$
and $\sigma=x_1<x_2<x_3<x_4$.  Formally, $T$ is defined as follows.
Let $v$ be the root of $T$.
The left subtree $T_l=T_{v_l}$ of $T$
is a right-linear vtree for $\{x_1,\ldots,x_n\}$ such that
the variable ordering induced by its left first traversal
is $\sigma$.  Similarly,
the right subtree $T_r=T_{v_r}$ of $T$
is a vtree for $\{y\}$.

We check that $C$ is an SDD respecting $T$.
\begin{itemize}
\item The subcircuits $C_{p_0}$, $C_{p_n}$, and $C_{p_{i,j}}$ are OBDDs respecting $\sigma$,
and hence SDDs respecting $T_l$ ($i=1,\ldots,n-1$, $j=0,1$).  This settles (S1)
\item The subcircuits $C_{s_0}$, $C_{s_n}$, and $C_{s_{i,j}}$ are
input gates labelled by a constant,
and hence SDDs respecting $T_r$ ($i=1,\ldots,n-1$, $j=0,1$).  This settles (S2).
\end{itemize}
Note how the construction crucially exploits the special position of $y$ in the vtree $T$,
while the circuit $C$ does not even read $y$.

The partitioning properties (S3)-(S5) follow by construction and Fact~\ref{fact:part}.
Therefore, $C$ is an SDD respecting $T$.  It remains to check that
$C$ has size cubic in $n$.

By construction, $C$ contains the $2n$ subcircuits $C_{p_0}$,
$C_{p_n}$, and $C_{p_{i,j}}$ for $i=1,\ldots,n-1$ and $j=0,1$;
each has size $O(n^2)$ by Proposition~\ref{prop:obdd-pi}
hence, altogether, they contribute $O(n^3)$ wires in $C$.
There remain $O(n)$ wires entering the output gate
and the gates $g_0,g_1,\ldots,g_m$.
\end{proof}

Combining Theorem~\ref{th:bryant} and Theorem~\ref{th:sdd-size},
we conclude that OBDDs and SDDs are exponentially separated
by the hidden weighted bit function.

\paragraph{Compressed SDDs vs OBDDs.} A slight variant
of the previous construction gives an exponential separation
of OBDDs and compressed SDDs.

Let $y_0,y_1,\ldots,y_n$ be fresh variables.  The boolean function
$F_n$ of the variables $x_1,\ldots,x_n,y_0,y_1,\ldots,y_n$,
called \emph{generalized hidden weighted bit} function, is defined by
\begin{equation}\label{eq:Fn}
(P_0 \wedge \neg y_0) \vee (P_n \wedge y_n) \vee \bigvee_{i=1}^{n-1} ((P_{i,0} \wedge \neg y_i) \vee (P_{i,1} \wedge y_i))\text{.}
\end{equation}

Notice that the form (\ref{eq:Fn}) is exactly as the form (\ref{eq:sdd-hwb-form}),
except that the $n$ copies of $\bot$ and the $n$ copies of $\top$
are replaced by the $2n$ pairwise nonequivalent formulas $\neg y_0$,
$y_n$, $y_i$, and $\neg y_i$ ($i=1,\ldots,n-1$),
so that (\ref{eq:Fn}) has indeed a compressed SDD implementation.   The details follow.

\begin{lemma}\label{lemma:sdd-size}
The $\mathcal{SDD}_c$ size of $F_n$ is $O(n^3)$.
\end{lemma}
\begin{proof}
We construct an NNF $C$ on input variables $X=\{x_1,\ldots,x_n,y_0,y_1,\ldots,y_n\}$
computing (\ref{eq:Fn}) along the lines of Theorem~\ref{th:sdd-size}.  The only modification
is that $C_{s_0}$ is an input gate labelled $\neg y_0$,
$C_{s_n}$ is an input gate labelled $y_n$,
$C_{s_{i,0}}$ is an input gate labelled $\neg y_i$,
and $C_{s_{i,1}}$ is an input gate labelled $y_i$ ($i=1,\ldots,n-1$).

We claim that $C$ is a compressed SDD respecting
a vtree $T$ for the variable set $X$ built exactly as in Theorem~\ref{th:sdd-size}
except that the right subtree $T_r=T_{v_r}$ of $T$
is a right-linear vtree for $\{y_0,y_1,\ldots,y_n\}$ such that
the variable ordering induced by its left first traversal is $\rho$.
See Figure~\ref{fig:vt-sdd} for the case $n=4$,
$\sigma=x_1<\cdots<x_4$, and $\rho=y_0<y_1<\cdots<y_4$.

To check that $C$ is a compressed SDD respecting $T$,
notice that the subcircuits $C_{p_0}$ and $C_{p_{i,j}}$ are OBDDs respecting $\sigma$,
and hence compressed SDDs respecting $T_l$ ($i=1,\ldots,n$, $j=0,1$),
and the subcircuits $C_{s_0}$ and $C_{s_{i,j}}$ are OBDDs respecting $\rho$,
and hence compressed SDDs respecting $T_r$ ($i=1,\ldots,n$, $j=0,1$).
Moreover, it is easily verified that the output gate of $C$ is compressed as by condition (C).
Hence $C$ is compressed.  The rest of the proof is identical to that of Theorem~\ref{th:sdd-size}.
\end{proof}

\begin{figure}[t!]
\centering
\begin{picture}(0,0)%
\includegraphics{vt-sdd_pspdftex}%
\end{picture}%
\setlength{\unitlength}{2901sp}%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\begin{picture}(3886,2468)(10883,-429)
\put(11830,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_3$}%
}}}}
\put(10930,569){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_1$}%
}}}}
\put(11380,119){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_2$}%
}}}}
\put(12730,-331){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$x_4$}%
}}}}
\put(12747,580){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$y_1$}%
}}}}
\put(13197,130){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$y_2$}%
}}}}
\put(13647,-320){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$y_3$}%
}}}}
\put(14547,-320){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$y_4$}%
}}}}
\put(12297,1030){\makebox(0,0)[lb]{\smash{{\SetFigFont{8}{9.6}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$y_0$}%
}}}}
\end{picture}%

\caption{The vtree for $F_4$ in the proof of Lemma~\ref{lemma:sdd-size}.}
\label{fig:vt-sdd}
\end{figure}

We now prove that the generalized hidden weighted bit function $F_n$ needs large OBDDs.

\begin{lemma}\label{lemma:obdd-size}
The $\mathcal{OBDD}$ size of $F_n$ is $2^{\Omega(n)}$.
\end{lemma}
\begin{proof}
Let $N$ be the size of a smallest $\mathcal{OBDD}$ on variables
$X=\{x_1,\ldots,x_n,y_0,y_1,\ldots,y_n\}$ computing $F_n$,
and let $\rho$ be any ordering of $X$
such that $\mathcal{OBDD}_\rho(F_n)=N$.

Let $G_n(x_1,\ldots,x_n)$ be the subfunction of $F_n$ where
$y_0,y_1,\ldots,y_n$ are replaced by $1$, in symbols:
\begin{equation}\label{eq:Gn}
G_n \equiv {F_n}(x_1,\ldots,x_n,1,1,\ldots,1)\text{.}
\end{equation}

Since conditioning (unboundedly many variables of) an OBDD
does not increase its size \cite[Theorem~2.4.1]{Wegener00}, we have that
\begin{equation}\label{eq:step-1}
\mathcal{OBDD}_{\rho}(G_n) \leq \mathcal{OBDD}_{\rho}(F_n)\text{.}
\end{equation}

We now claim that $G_n$ is the hidden weighted bit function on $n$ variables.
Indeed, by construction,
\begin{align*}
G_n &\equiv  F_n(x_1,\ldots,x_n,1,1,\ldots,1) \\
 & \equiv P_n \vee \bigvee_{i=1}^{n-1} P_{i,1
\end{align*}
which we already observed being equivalent to $\mathrm{HWB}_n$.  Therefore $\mathcal{OBDD}(G_n)=2^{\Omega(n)}$ by Theorem~\ref{th:bryant},
and in particular $\mathcal{OBDD}_\rho(G_n) \geq 2^{\Omega(n)}$.  By (\ref{eq:step-1}),
we are done.
\end{proof}

An exponential separation of OBDDs and compressed SDDs follows.

\begin{theorem}\label{th:exp-sep}
There exists an unbounded arity class of boolean functions $\mathcal{F}$
such that every arity $n$ function $f \in \mathcal{F}$ has $\mathcal{SDD}_c$ size in $O(n^3)$
and $\mathcal{OBDD}$ size in $2^{\Omega(n)}$.
\end{theorem}
\begin{proof}
Take $\mathcal{F}=\{ F_m \colon m \in \mathbb{N} \}$,
where $F_m$ is as in (\ref{eq:Fn}).  Then $F_m$ has
compressed $\mathcal{SDD}$ size $O(m^3)$ by Lemma~\ref{lemma:sdd-size}
and $\mathcal{OBDD}$ size $2^{\Omega(m)}$ by Lemma~\ref{lemma:obdd-size}.
Since $F_m$ has $n=2m+1$
variables, it follows that $F_m$ has $\mathcal{SDD}_c$ size in $O(n^3)$
and $\mathcal{OBDD}$ size in $2^{\Omega(n)}$.
\end{proof}

Notably, the function class giving the exponential separation
is as hard on compressed SDDs as the function class giving the quasipolynomial separation
(cubic in both cases, see Theorem~\ref{th:raz}).

\section{Discussion}\label{sect:disc}

We have shown that OBDDs and SDDs
are exponentially separated by
the hidden weighted bit function,
while OBDDs and compressed SDDs
are exponentially separated by the generalized hidden weighted bit function,
$F_n$ in (\ref{eq:Fn}), that contains the hidden weighted bit function as a subfunction:
\begin{equation}\label{eq:Fn-proj}
F_n(x_1,\ldots,x_n,1,1,\ldots,1)=\mathrm{HWB}_n(x_1,\ldots,x_n)\text{.}
\end{equation}
Separating OBDDs and SDDs by the hid\-den weight\-ed bit function, instead of by a function designed adhoc,
further corroborates the theoretical quality of SDDs.  As articulated by Bollig et al.\ \cite{BolligLSW99},
any useful extension of OBDDs is expected to implement the hidden weighted bit function efficiently.

The SDD $C$ described in the proof of Theorem~\ref{th:sdd-size} is not compressed,
because $\bot$ and $\top$ are reused $n$ times.
In view of the canonical construction of an SDD over a vtree \cite[Theorem~3]{Darwiche11}, it is readily observed that
compressing $C$ with respect to the vtree $T$ in the proof of Theorem~\ref{th:sdd-size} implies finding
a small SDD for $\mathrm{HWB}_n$ with respect to the left subtree of $T$,
that is, a small OBDD for $\mathrm{HWB}_n$; but this is impossible by Theorem~\ref{th:bryant}.  The fact
that compressing an SDD over its vtree
may increase the size exponentially has been observed already \cite[Theorem~1]{BroeckDarwiche15}.
We reiterate the observation here only because our argument is significantly shorter.

We conclude mentioning a nonobvious, and perhaps even unexpected,
aspect of our separation result.  An inspection of our construction
shows that SDDs are already exponentially more succinct than \emph{general OBDDs}
even allowing only \emph{one sentential decision} (and possibly many Shannon decisions); recall (\ref{eq:sdd-hwb-form}) and (\ref{eq:Fn}).
The construction by Xue et al.\ \cite{XueCD12} already uses \emph{nested sentential decisions}
even to separate \emph{OBDDs over a fixed variable ordering} from SDDs!

\paragraph{Questions.} We do not know whether the hidden weighted bit function has superpolynomial compressed
SDD size for all vtrees; a positive answer would separate compressed and uncompressed SDDs
in succinctness and, in view of Lemma~\ref{lemma:sdd-size} and (\ref{eq:Fn-proj}), would prove that
compressed SDDs do not support conditioning (of unboundedly many variables) in polynomial size.

In view of Theorem~\ref{th:raz}, it is natural to ask which SDDs are quasipolynomially simulated by OBDDs.
Our separating family shows that SDDs with unbounded fanin disjunctions cannot be quasipolynomially simulated by OBDDs.
On the other hand, recent work by Darwiche and Oztok essentially shows that
SDDs over binary disjunctions (fanin $2$) admit a quasipolynomial simulation by OBDDs \cite[Theorem~1]{OztokDarwiche15}.
In this light, it is tempting to conjecture that the above criterion is exact, that is, every SDD class over bounded fanin disjunctions
does indeed admit a quasipolynomial simulation by OBDDs.

Finally, a natural question arising in the context of the present work
is about the relative succinctness of SDDs and structured deterministic NNFs (see (\ref{eq:inclusions}));
to the best of our knowledge, the question is open. By Theorem~\ref{th:sdd-size},
at least we now know that the hidden weighted bit function is not a candidate to separate the two classes.

\section*{Acknowledgments}

The author thanks Igor Razgon for generously introducing
him to the problem addressed in this article, and an
anonymous reviewer for suggesting the comparison
with \cite{XueCD12} discussed in the conclusion.  This research was supported by the FWF Austrian Science Fund
(Parameterized Compilation, P26200).

\DeclareRobustCommand{\DE}[3]{#3}

redpajama_set_name: RedPajamaArXiv


text:
GDPR Information to be provided where personal data are collected from the data subject
Categories Blog, Free Data Protection Resources
Information to be provided where personal data are collected from the data subject
1. Where personal data relating to a data subject are collected from the data subject, the controller shall, at the time when personal data are obtained, provide the data subject with all of the following information:(a) the identity and the contact details of the controller and, where applicable, of the controller's representative;
(b) the contact details of the data protection officer, where applicable;
(c) the purposes of the processing for which the personal data are intended as well as the legal basis for the processing;(d) where the processing is based on point (f) of Article 6(1), the legitimate interests pursued by the controller or by a third party;
(e) the recipients or categories of recipients of the personal data, if any;
(f) where applicable, the fact that the controller intends to transfer personal data to a third country or international organisation and the existence or absence of an adequacy decision by the Commission, or in the case of transfers referred to in Article 46 or 47, or the second subparagraph of Article 49(1), reference to the appropriate or suitable safeguards and the means by which to obtain a copy of them or where they have been made available.
2. In addition to the information referred to in paragraph 1, the controller shall, at the time when personal data are obtained, provide the data subject with the following further information necessary to ensure fair and transparent processing:(a) the period for which the personal data will be stored, or if that is not possible, the criteria used to determine that period;
(b) the existence of the right to request from the controller access to and rectification or erasure of personal data or restriction of processing concerning the data subject or to object to processing as well as the right to data portability;
(c) where the processing is based on point (a) of Article 6(1) or point (a) of Article 9(2), the existence of the right to withdraw consent at any time, without affecting the lawfulness of processing based on consent before its withdrawal;
(d) the right to lodge a complaint with a supervisory authority;
(e) whether the provision of personal data is a statutory or contractual requirement, or a requirement necessary to enter into a contract, as well as whether the data subject is obliged to provide the personal data and of the possible consequences of failure to provide such data;
(f) the existence of automated decision-making, including profiling, referred to in Article 22(1) and (4) and, at least in those cases, meaningful information about the logic involved, as well as the significance and the envisaged consequences of such processing for the data subject.
3. Where the controller intends to further process the personal data for a purpose other than that for which the personal data were collected, the controller shall provide the data subject prior to that further processing with information on that other purpose and with any relevant further information as referred to in paragraph 2.
4. Paragraphs 1, 2 and 3 shall not apply where and insofar as the data subject already has the information.
privacad
Professor mr drs Romeo F. Kadir MA MSc LLM LLM (Adv) EMBA EMoC
First appointed Data Protection Officer (DPO) ever in the Netherlands (European Union) at a semi-public entity. Seasoned European Privacy and Data Protection Expert (20+ years of practical experience in EU Privacy and Data Protection Law, Business Management, Compliance and Ethics).
Studied European and International Law, Political Sciences and Business Administration. At Present EIPACC EADPP Professor European Privacy & Data Protection Law at Universitas Padjadjaran UNpad (Indonesia) and Honorary Visiting Research Fellow with O.P. Jindal Global University (New Delhi), Senior Associate Fellow with Vidhi Centre for Legal Policy (New Delhi), Lecturer Science Honours Academy and Lecturer at the International Molengraaff Institute, Utrecht University (UU, Netherlands). In 2010 he was founder of the first European Data Protection Academy focusing on privacy-only executive education.
Present Occupations in European Data Protection Law
President European Institute for Privacy, Audit, Compliance & Certification (EIPACC),
Vice-President European Association for Data Protection Professionals (EADPP),
Chair EADPP Certification Committee Data Protection Professionals,
Chair EADPP Academic Board,
Chair EADPP Expert Committee on Cybersecurity,
Chair EADPP Expert Committee on Artificial Intelligence (AI),
Member of the International Board of Experts with EuroPrivacy Certification Scheme (Geneva and Luxembourg),
President Supervisory Board of the Dutch Privacy Complaints Office (NPKI),
Rapporteur to UN Monitoring Commission Human Rights on behalf of the Dutch Privacy Foundation (SPN),
Author of 'Handbook DPO - A Practical Guide', Privacy Publishing Group (PPG),
Editor-in-Chief of 'Data Protection Dictionary', authored, edited and coordinated 'Handbook for the Data Protection Officer – A practical Guide', 'The Ultimate GDPR Business Guide – Six Volumes' and other relevant books in the field of privacy and data protection.
GDPR Transparent information, communication and modalities for the exercise of the rights of the data subject
GDPR Information to be provided where personal data have not been obtained from the data subject

redpajama_set_name: RedPajamaCommonCrawl


text:
Protest Against South Korean President Estimated to Be Largest Yet
End Times and Current Events > Forum > General Category > Current Events > Protest Against South Korean President Estimated to Be Largest Yet
Author Topic: Protest Against South Korean President Estimated to Be Largest Yet (Read 418 times)
http://www.nytimes.com/2016/11/26/world/asia/korea-park-geun-hye-protests.html?_r=0
SEOUL, South Korea — Hundreds of thousands of South Koreans filled central Seoul on Saturday to demand President Park Geun-hye's resignation, in what appeared to be the largest turnout yet in a series of weekly protests against the embattled leader.
Despite cold weather and the first snow of the season, a crowd that organizers estimated at 1.5 million gathered to denounce Ms. Park, who has been accused by prosecutors of helping a friend commit extortion and is facing the possibility of impeachment within weeks.
The police estimate of the turnout was much lower, at 260,000, but the crowd seemed larger than at an enormous rally in the capital two weeks earlier. It was the fifth consecutive Saturday marked by a large protest against the president.
The demonstrations have been peaceful and almost festive. Street vendors sold candles, mattresses and hot snacks on Saturday, and a few roadside shops gave protesters free coffee. Buddhist monks beat wooden gongs as they marched. Mothers showed up with children, or with pet dogs wrapped in padded vests, and young couples bundled in winter coats sang along as loudspeakers blared catchy tunes calling for Ms. Park's ouster.
One such song quoted from South Korea's Constitution: "The Republic of Korea shall be a democratic republic."
Prosecutors have identified Ms. Park as a criminal accomplice in the case of Choi Soon-sil, an old friend who has been charged with using her influence to coerce businesses into donating large sums to foundations that Ms. Choi controls. In news reports, Ms. Park has also been accused of letting Ms. Choi wield undue influence in state affairs.
Ms. Park, who cannot be prosecuted while in office, has apologized twice to the public over the scandal but has refused to resign as opposition lawmakers, major newspapers and some members of her own party have demanded.
Opposition parties hope to impeach her with the support of some lawmakers from her party. The National Assembly is expected to vote on an impeachment bill by Dec. 9.
No South Korean president has ever been removed from office through impeachment.
On Saturday, some protesters chanted, "Imprison Park Geun-hye!" as they marched toward the presidential Blue House. "Come out and surrender!" they shouted.
Hundreds of buses and thousands of police officers had been deployed to form barriers around the complex. One group of demonstrators was stopped just 200 yards from the presidential compound.
Protesters holding candles marched through central Seoul late into the night. Rock musicians performed on the main thoroughfare, replacing the lyrics of popular songs with phrases that criticized and ridiculed Ms. Park. Some people carried doctored images of Ms. Park in a prison uniform and handcuffed.
On smaller streets, citizens spoke to the crowd from the back of trucks. One teenage girl railed tearfully against Ms. Park for failing to respond effectively to the Sewol ferry disaster in 2014, which left more than 300 people dead, most of them teenagers.
She also criticized the government-written history textbooks that Ms. Park's administration has said it plans to issue for use in all middle and high schools starting next year.
Protesters accused Ms. Park of trying to take South Korea back to the time when it was ruled by military dictators, including her father, Park Chung-hee, and the practice of shaking down businesses was commonplace.
At one point, at the suggestion of organizers, the protesters all blew out their candles to symbolize the darkness into which, they said, Ms. Park has led the country.
Many protesters said they wanted Ms. Park to be impeached, providing a dramatic end to her tenure.
"What we have seen happening at the Blue House is just like a soap opera," said Kim Yong-jin, a high school senior. "We just hope that it ends like a soap opera — with poetic justice."
Re: Protest Against South Korean President Estimated to Be Largest Yet
http://www.cnn.com/2016/12/09/asia/south-korea-park-geun-hye-impeachment-vote/index.html
South Korea's parliament votes to impeach President Park Geun-hye
Seoul, South Korea (CNN)Lawmakers in South Korea's National Assembly voted overwhelmingly Friday to impeach President Park Geun-hye over a corruption scandal. The vote was 234-56, with six abstentions.
The country's Constitutional Court will now deliberate the impeachment motion, a process that could take up to 180 days.
Park apologized on national TV following the vote, saying she was careless and had caused a "big national chaos" -- an apparent reference to her sharing classified information with a confidante lacking security clearance.
"I solemnly accept the voices of the National Assembly and the people and sincerely hope that the current confusion will come to an end in an orderly manner," said Park, the country's first female leader.
"... I will respond to the impeachment judgment of the constitutional court and the investigation of the special prosecutors, following the procedures set by the constitution and the law with (a) calm mind-set and then will accept its decision."
JulesPi
I'm impressed by South Korean people and their standard of democracy. Imagine what terror had to be done to the North Koreans to enslave them like that.
tennis shoe
Re: Korean Churches
Quote from: JulesPi on October 13, 2018, 12:23:12 pm
God has blessed that country tremendously with revival since the turn of the century. From Wonsan to Pyongyang and beyond - regardless of wars and civil unrest, He has established one of the most passionately devout and serious churches I have ever encountered.


text:
Lestret de Malacca (en malai Selat Melaka, en indonesi Selat Malaka, en tailandèsช่องแคบ มะละกา, en tàmil மலாக்கா நீரிணை, Malākkā nīriṇai, en xinès: 馬六甲 海峽 / 马六甲 海峡)) és un braç de mar que separa la península de Malacca de l'illa indonèsia de Sumatra. D'una longitud d'uns 930 km, una amplada mínima de 38 km i una fondària mínima de 25 m, és la via de comunicació principal entre l'oceà Índic i el Pacífic, i més concretament entre la mar d'Andaman i la mar de la Xina Meridional. Rep el nom del sultanat de Malaca que va governar l'arxipèlag entre els anys 1400 i 1511, el centre d'administració del qual es trobava a l'estat actual de Malaca, Malàisia.

Des de la perspectiva econòmica i estratègica, l'estret de Malaca és una de les vies marítimes més importants del món.

De mitjana, 250 vaixells passen cada dia a través de l'estret, que és una ruta de navegació importantíssima, ja que vincula tota la mar de la Xina amb l'oceà Índic i Europa a través del canal de Suez. A la part central és on es troba la seva mínima profunditat, cosa que condiciona el calat dels vaixells que el travessen. Els vaixells de mida i calat màxims aptes per travessar l'estret es coneixen com a Malaccamax (limitats a un calat de 20 m).

Història
Els primers comerciants d'Aràbia, Àfrica, Pèrsia i els regnes del sud de l'Índia van arribar a Kedah abans d'arribar a Guangzhou. Kedah servia de port occidental a la península de Malacca. Comerciaven amb articles de vidre, alcanfor, cotó, brocats, ivori, sàndal, perfums i pedres precioses. Aquests comerciants navegaven fins a Kedah amb el vent del monsó entre juny i novembre. Retornaven entre desembre i maig. Kedah proporcionava allotjament, traginers, vaixells petits, basses de bambú, elefants, així com recaptació d'impostos per a les mercaderies que havien de transportar-se per terra cap als ports orientals de la península malaia com Langkasuka i Kelantan. Després del segle X, els vaixells de la Xina van començar a comerciar en aquests ports comercials orientals. Kedah i Funan van ser ports famosos al llarg del segle VI, abans que el transport marítim comencés a utilitzar l'estret de Malacca com a ruta comercial.

Al segle VII, l'imperi marítim de Srivijaya amb base a Palembang (Sumatra) va pujar al poder, i la seva influència es va estendre a la península malaia i Java. L'imperi va obtenir un control eficaç en dos punts principals del sud-est asiàtic marítim; l'estret de Malacca i l'estret de la Sonda. Llançant una sèrie de conquestes i incursions en ports rivals potencials a banda i banda de l'estret, Srivijaya va assegurar la seva dominació econòmica i militar a la regió, que va durar uns 700 anys. Srivijaya va obtenir grans beneficis amb el lucratiu comerç d'espècies, per exemple. El sistema de comerç tributari amb la Xina i el comerç amb comerciants indis i àrabs. L'estret de Malacca es va convertir en una important ruta comercial marítima entre l'Índia i la Xina. La importància de l'estret de Malacca a les xarxes comercials mundials va continuar fins a segles posteriors amb l'ascens del sultanat de Malaca al segle XV, el sultanat de Johor i l'ascens de la moderna ciutat-estat de Singapur.

Des del segle XVII, l'estret ha estat el principal canal marítim entre l'oceà Índic i l'oceà Pacífic. Diverses grans potències regionals han gestionat l'estret durant diferents períodes històrics.

A principis del , els imperis holandès i britànic van establir una línia fronterera arbitrària a l'estret i van prometre caçar pirates pels seus bàndols respectius; aquesta línia es va convertir en la frontera actual entre Malàisia i Indonèsia.

Importància econòmica

L'estret és el principal canal marítim entre l'Oceà Índic i l'Oceà Pacífic, que uneix les principals economies asiàtiques com l'Índia, Tailàndia, Indonèsia, Malàisia, Filipines, Singapur, Vietnam, Xina, Japó, Taiwan i Corea del Sud. L'estret de Malaca forma part de la Ruta de la Seda Marítima que va des de la costa xinesa cap a l'extrem sud de l'Índia fins a Mombasa, des d'allà pel mar Roig a través del canal de Suez fins a la Mediterrània, i d'allà fins a la regió de l'Adriàtic superior fins a Trieste, al nord d'Itàlia, amb les seves connexions ferroviàries a Europa central i el mar del Nord. Més de 94.000 vaixells  passen per l'estret cada any (2008), cosa que el converteix en l'estret més transitat del món, transportant al voltant del 25% de les mercaderies comercialitzades al món, inclosos petroli, productes manufacturats xinesos, carbó, oli de palma i cafè indonesi. Aproximadament una quarta part del petroli transportat per mar passa per l'estret, principalment des de proveïdors del Golf Pèrsic fins als mercats asiàtics. El 2007, s'estima que es transportaven 13,7 milions de barrils al dia a través de l'estret, augmentant fins a 15,2 milions de barrils al dia el 2011. A més, també és un dels punts d'estrangulament més congestionats del món perquè s'estreny a només 2,8 km d'amplada al canal Phillip (a prop del sud de Singapur).

El calat d'alguns dels vaixells més grans del món (principalment petroliers) supera la profunditat mínima de l'estret de 25 metres. Aquest punt poc profund es produeix a l'estret de Singapur. La mida màxima d'un vaixell que pot passar per l'estret es coneix com Malaccamax. El següent pas més proper a l'est, l'estret de la Sonda entre Sumatra i Java, és encara més reduït i estret, cosa que significa que els vaixells que superen el Malaccamax han de desviar-se uns quants milers de milles nàutiques i utilitzar l'estret de Lombok, l'estret de Macassar, el pas de Sibutu o l'estret de Mindoro.

Referències

Vegeu també
 Pirateria a l'estret de Malacca

Malacca
Geografia de Sumatra
Geografia de Malàisia
Oceà Índic

redpajama_set_name: RedPajamaWikipedia


text:
Boone County is a county in the U.S. state of West Virginia. As of the 2020 census, the population was 21,809. Its county seat is Madison. Boone County is part of the Charleston, WV Metropolitan Statistical Area. Leading industries and chief agricultural products in Boone County include coal, lumber, natural gas, tobacco, and strawberries.

History
The county was formed in 1847 with territories annexed from Kanawha, Cabell, and Logan counties. It was named for frontiersman Daniel Boone, who lived in the Great Kanawha Valley from 1789 until 1795.

In 1863, West Virginia's counties were divided into civil townships, with the intention of encouraging local government.  This proved impractical in the heavily rural state, and in 1872 the townships were converted into magisterial districts.  Boone County was divided into five districts: Crook, Peytona, Scott, Sherman, and Washington.  Between 1980 and 1990, the county was redivided into three magisterial districts: District 1, District 2, and District 3.

On February 1, 2006, two fatal mining accidents occurred in the communities of Uneeda and Wharton in Boone County. These two deaths with the addition of January's Sago Mine disaster and the Aracoma Alma Mine disaster caused West Virginia Governor Joe Manchin to close all of West Virginia's mines in a "mine safety stand-down."

Geography
Boone County lies in the central southwestern part of West Virginia. Its terrain consists of low wooded mountains, carved with drainages. The terrain slopes to the north and west, with its highest point at its south corner, at 3,212' (979m) ASL. The county has a total area of , of which  is land and  (0.3%) is water.

Major highways

  U.S. Highway 119
  West Virginia Route 3
  West Virginia Route 17
  West Virginia Route 85
  West Virginia Route 94
  West Virginia Route 99

Adjacent counties

 Kanawha County - northeast
 Raleigh County - east
 Wyoming County - south
 Logan County - west
 Lincoln County - northwest

Demographics

2010 census
As of the census of 2010, there were 24,629 people, 9,928 households, and 7,014 families in the county. The population density was 49.1/sqmi (18.9/km2). There were 11,070 housing units at an average density of 22.1/sqmi (8.51/km2). The racial makeup of the county was 98.5% white, 0.5% black or African American, 0.1% Asian, 0.1% American Indian, 0.2% from other races, and 0.6% from two or more races. Those of Hispanic or Latino origin made up 0.4% of the population. In terms of ancestry, 15.4% were German, 13.3% were American, 12.9% were Irish, and 8.3% were English.

Of the 9,928 households, 32.2% had children under the age of 18 living with them, 54.0% were married couples living together, 11.3% had a female householder with no husband present, 29.4% were non-families, and 25.7% of all households were made up of individuals. The average household size was 2.47 and the average family size was 2.94. The median age was 40.7 years.

The median income for a household in the county was $39,783 and the median income for a family was $47,981. Males had a median income of $51,740 versus $32,110 for females. The per capita income for the county was $20,457. About 15.6% of families and 19.3% of the population were below the poverty line, including 25.9% of those under age 18 and 13.4% of those age 65 or over.

2000 census
As of the census of 2000, there were 25,535 people, 10,291 households, and 7,460 families in the county. The population density was 50.9/sqmi (19.6/km2). There were 11,575 housing units at an average density of 23.1/sqmi (8.9/km2). The racial makeup of the county was 98.53% White, 0.65% Black or African American, 0.12% Native American, 0.07% Asian, 0.02% Pacific Islander, 0.07% from other races, and 0.54% from two or more races. 0.46% of the population were Hispanic or Latino of any race.

The largest ancestry groups in Boone County are English (13%), Irish (12%) and German (11%).

There were 10,291 households, out of which 31.10% had children under the age of 18 living with them, 57.50% were married couples living together, 10.50% had a female householder with no husband present, and 27.50% were non-families. 24.60% of all households were made up of individuals, and 11.00% had someone living alone who was 65 years of age or older. The average household size was 2.47 and the average family size was 2.92.

The county contained 23.20% under the age of 18, 9.00% from 18 to 24, 28.00% from 25 to 44, 26.30% from 45 to 64, and 13.60% who were 65 years of age or older. The median age was 39 years. For every 100 females, there were 95.50 males. For every 100 females age 18 and over, there were 92.50 males.

The median income for a household in the county was $25,669, and the median income for a family was $31,999. Males had a median income of $34,931 versus $19,607 for females. The per capita income for the county was $14,453. About 18.30% of families and 22.00% of the population were below the poverty line, including 27.90% of those under age 18 and 13.90% of those age 65 or over.

Politics
With the exception of the 1972 Nixon landslide, Boone County voted Democratic in every presidential election from 1924 until 2012. In 2012, Republican Mitt Romney won over sixty percent of the vote in the process of becoming the first presidential candidate to sweep every county in the state. Also in 2012, in the state's Democratic primaries, Boone County was one of the West Virginia counties that voted for eccentric perennial candidate Keith Russell Judd, who at the time was still in prison on felony charges, over incumbent president Barack Obama.

Education

Madison
 Brookview Elementary School
 Madison Elementary School
 Ramage Elementary School
 Madison Middle School
 Scott High School

Van
 Van Elementary School
 Van Jr./Sr. High School

Seth
 Ashford-Rumble Elementary School
 Sherman Elementary School
 Whitesville Elementary School
 Sherman Junior High School
 Sherman Senior High School

Communities

City
 Madison (county seat)

Towns
 Danville
 Sylvester
 Whitesville

Magisterial districts
 District 1
 District 2
 District 3

Census-designated places

 Comfort
 Greenview
 Racine
 Twilight
 Van

Unincorporated communities

 Andrew
 Ashford
 Bald Knob
 Bandytown
 Barrett
 Bigson
 Bim
 Bloomingrose
 Blue Pennant
 Bob White
 Bradley
 Brushton
 Cameo
 Cazy
 Clinton
 Clothier
 Coopertown
 Dartmont
 Drawdy
 Easly
 Eden
 Elk Run Junction
 Emmons (part)
 Foch
 Foster
 Fosterville
 Garrison
 Gordon
 Grippe
 Havana
 Hewett
 Hopkins Fork
 Janie
 Jeffrey
 Julian
 Keith
 Kirbyton
 Kohlsaat
 Lanta
 Lick Creek
 Lindytown
 Low Gap
 Manila
 Marnie
 Marthatown
 Maxine
 Milltown
 Morrisvale
 Nellis
 Nelson
 Onego
 Orgas
 Ottawa
 Peytona
 Pondco
 Powell Creek
 Prenter
 Price Hill
 Quinland
 Ramage
 Ridgeview
 Rumble
 Secoal
 Seth
 Sharlow
 South Madison
 Turtle Creek
 Uneeda
 Washington Heights
 West Junction
 Wharton
 Williams Mountain

Notable people
 Hasil Adkins, musician
 Billy Edd Wheeler, songwriter
 D. Ray White, mountain dancer, father of Jesco White
 Jesco White, "the Dancing Outlaw," mountain dancer, son of D. Ray White

See also
 Hobet Coal Mine
 Fork Creek Wildlife Management Area
 The Wild and Wonderful Whites of West Virginia, a documentary film set in Boone County
 National Register of Historic Places listings in Boone County, West Virginia
 Upper Big Branch Miners Memorial, a roadside memorial in Whitesville to honor the 29 men killed in an explosion at the Upper Big Branch Coal Mine on April 5, 2010.

References

External links
 Boone County Community and Economic Development Office
 WVGenWeb Boone County

1847 establishments in Virginia
Populated places established in 1847
Charleston, West Virginia metropolitan area
Counties of Appalachia


text:
Q: The program consists of two buttons to increase and decrease the number of store of value I need a program that includes two buttons to increase and decrease the number and display it
As well as storage and display number after close and open app

A: for storage data you can use angular-local-storage for get https://github.com/grevory/angular-local-storage
for load data use $scope.storageValue = localStorageService.get('StoreData');
for save data use localStorageService.set('StoreData',$scope.storageValue);
full code:
<!DOCTYPE html>

    <meta charset="utf-8">
    <meta name="viewport" content="initial-scale=1, maximum-scale=1, user-scalable=no, width=device-width">

    <link href="lib/ionic/css/ionic.css" rel="stylesheet">
    <link href="css/style.css" rel="stylesheet">

    <ion-content>

                Number : {{storageValue}}

                <button class="button button-positive" ng-click="add()">
                  +
                </button>
                <button class="button button-positive" ng-click="sub()">
                  -
                </button>

  </ion-content>

pic

redpajama_set_name: RedPajamaStackExchange


For homeowners looking to add extra value to their property, it can be overwhelming considering where to start. For affordable ways to spruce up the look and feel of a property, here's a few tips to get you started. With all for under $500, these cost-saving, value creating hints will be sure to give your home update that extra zing it needs to enter the market with a greater promise of reward.
Any improvements to the home, especially when considering selling or renting a property, should start outside. This is where the first impression of the entire property starts. A messy, un-cared for yard impacts negatively on the entire home. To add more curb appeal, for just a few hundred dollars, you can hire a lawn maintenance company to help get it up to par. Add in a few plants and features, and this will go a long way.
An integrated home where all rooms and spaces flow creates sense of harmony for the home. If you are on a budget, however, and cannot afford to remodel and redecorate every space, it can be difficult to choose what to prioritize. A great tip is knowing that both the kitchen and the bathrooms are considered as highly integral in the decision making process. It can be the point of difference for buyers choosing between similar properties. Small changes such as fresh paint, new cupboards, or just redecorating can make these spaces shine.
As modern technology moves forward in every industry, the home lifestyle and building sector is jumping on the train of the various green products and systems. Not only is it a great selling point to offer solar panel heating or water filter systems, but it also gives back to the environment. Energy efficient inclusions to the home don't have to break the bank, even lighting changes can add that extra value for an accessible budget.
If you want to do some more upscale improvements to your home, try updating the structural quality in your home with Simpson Strong Tie Connectors.


text:
You are here: Home > Football Tips > Arsenal Must Salvage Season in FA Cup Tie at Hull
Arsenal Must Salvage Season in FA Cup Tie at Hull
Eric Roberts 2016-03-07 in Football Tips
Odds display preferences
Decimal (6.00)
Fractional (5/1)
US/Moneyline (+500)
HongKong (5.00)
Indonesian (5.00)
Malaysian (-0.20)
It's been a torrid few weeks for Arsenal and Arsene Wenger, and once again they've lived up to the tag of 'bottlers' in the title race. Incredibly, Arsene Wenger's future also appears to be in doubt with a growing number of Arsenal fans calling for the Frenchman's head after a winless run of five games.
To fans of other clubs that seems ridiculously harsh considering the North London club are sitting third in the Premier League, just eight points off the top, and as things stand are still involved in both Champions League and FA Cup. However, with a 2-0 deficit to make up against Barcelona at the Nou Camp it is not a huge stretch to suggest that Arsenal's Champions League campaign is over for yet another season, and having been within touching distance of Leicester at the top of the table, they've dropped away with a whimper. While the FA Cup may never be the highest on Wenger's agenda, all of a sudden this game has taken on extra importance, and a defeat could see him staring the sack in the face.
For Hull this repeat of last year's final may not be at the forefront of their priorities either, with promotion from the Championship back to the Premier League this season's ultimate aim. Steve Bruce has the Tigers positioned in 3rd place in the table but the 1-0 defeat at Birmingham last time out has left them with a three point gap to make up on Middlesbrough in 2nd, and Bruce will probably have eyes on the upcoming double-header against MK Dons and Nottingham Forest at home.
Neither side is likely to field a first-string team, and with that in mind Arsenal look to be the best bet at 83/100 1.83 -120 0.83 -1.20 0.83 with Coral, Paddy Power and William Hill
The abuse Arsene Wenger will receive if his side fail to win here doesn't bear thinking about for the Arsenal faithful, and realistically this is their best chance of silverware and salvaging something from the season. The likes of Joel Campbell, Theo Walcott and Olivier Giroud were all left on the bench for the 2-2 North London derby with Spurs, and if those three line up they should have more than enough quality for Hull. Alexis Sanchez was back among the goals at White Hart Lane, with his strike securing a point for the 10-man Gunners, and there is a possibility Wenger will give him a start in order to boost the confidence and build a goal-scoring run, but one would think it's more likely that the Chilean star will be kept in reserve for the rest of the Premier League season as Arsenal try to make up the gap on Leicester and Spurs.
Steve Bruce has a fully fit squad to choose from but the decision he has to make is whether to play his big guns in search of revenge for the Wembley defeat of two years ago, or whether to turn to his back-up players and keep his powder dry for the promotion push. It's a tough call to make, but the prize of Premier League football is so much greater than a quarter final against Watford on Sunday – which is what awaits the winner of this replay.
In terms of form it's a surprise that the two clubs have managed just one win between them in the last ten games combined. Hull have had three 0-0 draws in their last five against Brighton, Sheffield Wednesday and Arsenal in the first tie of this cup clash, and they've interspersed those with a 1-0 win at Ipswich and a 1-0 loss at Birmingham. Meanwhile the Gunners have drawn against Hull and Spurs, with damaging defeats to Barcelona in the Champions League and Swansea and Manchester United in the Premier League. At least Arsenal can say they've found the net five times in their last three games, whereas Hull have only managed a single goal in the last five matches.
Goalscorer Odds
As well as backing Arsenal to win the game, we also fancy a side bet on Olivier Giroud to come good and notch the first goal at a tempting 9/2 5.50 +450 4.50 4.50 -0.22 with Bet365, Skybet and Paddy Power
The big Frenchman has lost his form of late, going ten games without a goal and has recently been replaced in the starting line up with the returning Danny Welbeck. However, he came on against Spurs and had a big impact, looking threatening and contributing to Arsenal getting back into the game despite being down to ten men. He's got a point to prove and assuming he gets the nod to start this one, he will be dangerous from the outset. Even if Steve Bruce opts to field his strongest line-up, we'd still expect Arsenal to dominate the ball and Giroud should get chances to get back amongst the goals.
Tips Summary
Arsenal to beat Hull
Tuesday 8th March, 19:00 GMT
Odds: 83/100 1.83 -120 0.83 -1.20 0.83
Olivier Giroud to score the first goal
Odds: 9/2 5.50 +450 4.50 4.50 -0.22
Burnley Far Too Big to Beat Fulham in Championship
Get Your Kicks out of Real-Roma Corners
Eric has been a sports journalist for over 20 years and has travelled the world covering top sporting events for a number of publications. He also has a passion for betting and uses his in-depth knowledge of the sports world to pinpoint outstanding odds and value betting opportunities.
MMA Betting Tips
MMA is a great sport to bet on with loads of markets available. However, it can be difficult to call, so why not see what our experts think of upcoming fights?
Our expert team have years of experience when it comes to betting on horses and they cover all angles to beat the bookies. See their latest tips here.
NFL Betting Picks
Betting on the NFL is great fun, but it's not always easy. Our experts have years of experience and can help you get the edge over sportsbooks for NFL betting.
NBA Betting Tips
Games come thick and fast in the NBA and it can be a hard league to call. Our team of experts have got you covered though. See their latest picks here.


text:
Q: Adding a
A: The node value is just text, its not like inner HTML where you can specify a string with markup in it. With a document fragment you can get something close to that, but you're setting xml rather than html so your html would have to be valid xml.
$xpath = new DOMXpath($doc);
$nodes = $xpath->query( "//div[@class = 'ad_stream_hd']");
if ($nodes->length > 0){
    $node = $nodes->item($nodes->length-1);
    $fragment = $doc->createDocumentFragment();
    $fragment->appendXML('<script type="text/javascript" src="http://clkrev.com/adServe/banners?tid=SPORTVE158X21&size=158x21" ></script>');
    $node->appendChild($fragment);
}

A: Edit: right way to iterate DOMNodeList:
$nodes_length = $nodes->length;
for ($i=0; $i < $nodes_length; $i++) {
    $nodes->item($i)->nodeValue = '<script type="text/javascript" src="http://clkrev.com/adServe/banners?tid=SPORTVE158X21&size=158x21" ></script>';
}


WHen you get nAKED, you should display IT with the most luxurious Products.
taking the photo album to the next level. these stunning, lay flat albums will keep your gorgeous images looking timeless for years to come.
that's right girl. you are the star of this show. i'll create a custom video using your images set to the perfect song. it's the perfect compliment to your boudoir album, glass heirloom box or collection.


So having struggled with our spiritual growth with the Devil, the Ego, The Tower, and Awakening, our Dreamer now comes to 17-The Star.
In both Rider-Waite (RW) and Angel Tarot, we find a beautiful woman with two containers for water. In the RW tarot, the woman is naked and in Angel tarot, she is represented by Archangel Jophiel. The Star represents a time for respite. It indicates we are exactly where we should be, doing what we should be doing. It may be that we were taking on a lot of other people's junk and that is why we had the last few cards before The Star–to take a closer look at who we really are and compare it with who we came to be. It seems much easier to follow the crowd and be who others want us to be. But that all ends with The Star. By now our journey has left us so exhausted that we can't help but be the unique and beautiful creatives we are all meant to be. We have a purpose to fulfill while we are here in physical form. At this point, we begin to see ourselves as whole and complete. We have been reminded of our mission and purpose.
The symbolism of the star is appropriate for this card. Sailors have used the stars as guidance to tell us where we are and where we are going for eons. Archangel Jophiel is pouring water in two places. The first is a vast openness which represents universal consciousness. The other jug is emptying out into 5 streams, which represents the 5 senses. Archangel Jophiel has no worries that she will run out of the water. The Source is eternal. In the RW tarot, the large yellow star represents Universal consciousness and the 7 stars in both cards represent the 7 chakras.


During his 14 years in the NBA, David Robinson made 10 All-Star teams, won two championships, and earned Rookie of the Year and MVP awards. He played his entire career with the San Antonio Spurs, battling for rebounds against fellow Hall of Famers Hakeem Olajuwon, Patrick Ewing, and Shaquille O'Neal.
Fifteen years into retirement, Robinson is still fit and strong. He doesn't follow the 5,000-calorie diet of his youth or play 82-game seasons, but the 52-year-old still eats well and trains hard.
"Consistency is the real challenge," he says. "You can't half commit to being in shape or healthy—you have to be fully committed to it and really incorporate it into your life." He spoke with Furthermore about kickboxing, yoga, and the biggest change to his diet.
The Training Regimen:When I was playing in the NBA, I did my workouts to exhaustion. Now, it's more like I exercise until I'm tired or hungry. Back then, I was constantly trying to improve, grow, and get strong, but I don't have as big of a reason to push myself to that point anymore. I'm more focused on maintaining my fitness and overall health. I enjoy working out now because it's less stressful.
I do a lot of yoga, which was so big for me during my career. It helped me with my breathing, sleeping, and injury prevention. Yoga is a great workout in itself. I like that I have total control over how deeply I want to go into each stretch and how patient I am throughout a routine. No matter where I am, I can do some moves without relying on anyone else to get it done.
A main part of my workouts now is kickboxing. My former teammate Tim Duncan got me into it. I love that it challenges me in multiple ways. It tests my reflexes, my strength, and my strategic thought process in the moment, and engages the body as well as the mind. If you're going to kickbox, I recommend you do it with people you trust. It's a very violent sport, and it's easy to get competitive.
I also enjoy biking because it's a relaxing, solid workout, and it gets you out in the real world. Everyone spends so much time in the virtual world, and biking gives me a break from that.The Nutrition Regimen:The biggest change for me over the years is how many calories I take in. When I was playing, I'd try to have 5,000 to 6,000 calories per day, and I easily burned it off.
I keep my diet simple: clean protein, greens, vegetables, and healthy carbs. I stay away from soda, dressings, and other high-sugar foods. Sometimes I fuel my workouts with shakes full of healthy proteins and fruit.
The Regeneration Regimen:Recovery is key to long-term fitness and health. I used to do a lot of what I call pre-workout stuff, like getting in hot tubs. As I got older, rest became the most important thing. I always underestimated its power earlier in my career. Being young, you think you can stay up all hours of the night and get up early the next morning, but your body needs sleep to recover. If you don't sleep well, it's hard to sustain any kind of effort. I use yoga as a form of exercise, but also as a form of regeneration.
What's Next: I love being an ambassador for the NBA, traveling for basketball-related events, and talking with people about the importance of sports. I don't have any trips coming up, but I'm looking forward to doing more with the league and using the sport to bridge cultures around the world.


Dessert is the most exciting part of a meal for my husband. I prefer to have fruit 90% of the time, on the other hand, he would rather have cakes, cookies or ice-cream 80% of the time.
There are many desserts out there that combine cake and ice-cream, or cake and fruit, even all three together. I thought I'd try and make one. I already had lemon cake with raisins in it that I had baked a couple of days before.
I used plain vanilla ice-cream.
Pick a good one by the way, one that's nice and creamy.
I had mine with mango instead of cake.
and ice-crean on top. yum!