text:
\section{Introduction}\label{intro}

Noncommutative computation, introduced in complexity theory by Hyafil
\cite{Hya77} and Nisan \cite{N91}, is an important subfield of algebraic
complexity theory. The main algebraic structure of interest is the free
noncommutative ring $\F\angle{X}$ over a field $\F$, where
$X=\{x_1,x_2,\cdots,x_n\}$ is a set of free noncommuting variables. A central
problem is Polynomial Identity Testing which may be stated as follows:

Let $f\in \F \angle{X}$ be a polynomial represented by a noncommutative
arithmetic circuit $C$.  The circuit $C$ can either be given by a black box
(using which we can evaluate $C$ on matrices with entries from $\F$ or an
extension field), or the circuit may be explicitly given. The algorithmic
problem is to check if the polynomial computed by $C$ is identically zero.
We recall the formal definition of a noncommutative arithmetic circuit.

\begin{definition}\label{ckt}
  An \emph{arithmetic circuit} $C$ over a field $\F$ and
  indeterminates $X=\{x_1,x_2,\cdots,x_n\}$ is a directed acyclic
  graph (DAG) with each node of indegree zero labeled by a variable or
  a scalar constant from $\F$: the indegree $0$ nodes are the input
  nodes of the circuit. Each internal node of the DAG is of indegree
  two and is labeled by either a $+$ or a $\times$ (indicating that it
  is a plus gate or multiply gate, respectively). Furthermore, the two
  inputs to each $\times$ gate are designated as left and right inputs
  which prescribes the order of multiplication at that gate. A gate of
  $C$ is designated as \emph{output}. Each internal gate computes a
  polynomial (by adding or multiplying its input polynomials), where
  the polynomial computed at an input node is just its label. The
  \emph{polynomial computed} by the circuit is the polynomial computed
  at its output gate.
\end{definition}

When the multiplication operation of the circuit in
Definition~\ref{ckt} is \emph{noncommutative}, it is called a
\emph{noncommutative arithmetic circuit} and it computes a polynomial
in the free noncommutative ring $\F\angle{X}$.  Since cancellation of
terms is restricted by noncommutativity, intuitively it appears
noncommutative polynomial identity testing would be easier than
polynomial identity testing in the commutative case. This intuition is
supported by fact that there is a deterministic polynomial-time
white-box $\pit$ algorithm for noncommutative ABP \cite{RS05}. In the
commutative setting a deterministic polynomial-time PIT for ABPs would
be a major breakthrough.\footnote{The situation is similar even in the
  lower bound case where Nisan proved that noncommutative determinant
  or permanent polynomial would require exponential-size algebraic
  branching program \cite{N91}.}  However, there is little progress
towards obtaining an efficient deterministic $\pit$ for general
noncommutative arithmetic circuits. For example, the problem is open
even for noncommutative \emph{skew} circuits.

If \emph{associativity} is also dropped then it turns out that $\pit$
becomes easy, as we show in this work. More precisely, we consider the
free noncommutative and nonassociative ring of polynomials $\F\{X\}$,
$X=\{x_1,x_2,\ldots,x_n\}$, where a polynomial is an $\F$-linear
combination of monomials, and each monomial comes with a bracketing
order of multiplication. For example, in the nonassociative ring
$\F\{X\}$ the monomial $(x_1(x_2 x_1))$ is different from monomial
$((x_1 x_2)x_1)$, although in the associative ring $\F\angle{X}$ they
clearly coincide.

When the multiplication operation is both noncommutative and
nonassociative, it is called a \emph{nonassociative noncommutative
 circuit} and it computes a polynomial in the free nonassociative
noncommutative ring $\F\{X\}$. Previously, the nonassociative
arithmetic model of computation was considered by Hrubes, Wigderson,
and Yehudayoff \cite{HWY10b}. They showed completeness and explicit
lower bound results for this model.  We show the following result
about $\pit$.

\begin{itemize}
\item  Let $f(x_1,x_2,\ldots,x_n)\in\F\{X\}$ be a degree $d$ polynomial
  given by an arithmetic circuit of size $s$. Then in deterministic
  $\poly(s,n,d)$ time we can test if $f$ is an identically zero
  polynomial in $\F\{X\}$.
\end{itemize}

\begin{remark}
  We note that our algorithm in the above result does not depend on
  the choice of the field $\F$. A recent result of Lagarde et
  al.\ \cite{LMP16} shows an exponential lower bound, and a
  deterministic polynomial-time $\pit$ algorithm over $\R$ for
  noncommutative circuits where all parse trees in the circuit are
  isomorphic. We also note that in \cite{AR16} an exponential lower
  bound is shown for set-multilinear arithmetic circuits with the
  additional semantic constraint that each monomial has a unique parse
  tree in the circuit (but different monomials can have different
  parse trees).
\end{remark}

Next, we consider polynomial factorization in the ring
$\F\{\ex\}$. Polynomial factorization is very well-studied in the
commutative ring $\F[X]$: Given an arithmetic circuit $C$ computing a
multivariate polynomial $f\in\F[\ex]$ of degree $d$, the problem is to
efficiently compute circuits for the irreducible factors of $f$. A
celebrated result of Kaltofen \cite{Kal89} solves the problem in
randomized $\poly(n,s,d)$ time. Whether there is a polynomial-time
deterministic algorithm is an outstanding open problem. Recently, it
is shown (for fields of small characteristic and characteristic zero)
that the complexity of deterministic polynomial factorization problem
and the $\pit$ problem are polynomially equivalent \cite{KSS15}. A
natural question is to determine the complexity of polynomial
factorization in the noncommutative ring $\F\angle{X}$. The free
noncommutative ring $\F\angle{X}$ is not even a \emph{unique
  factorization domain} \cite{Cohn}. However, unique factorization
holds for homogeneous polynomials in $\F\angle{X}$, and it is shown in
\cite{AJR15} that for homogeneous polynomials given by noncommutative
circuits, the unique factorization into irreducible factors can be
computed in randomized polynomial time (essentially, by reduction to
the noncommutative PIT problem).

In this paper, we note that the ring $\F\{X\}$ is a \emph{unique
  factorization domain}, and given a polynomial in $\F\{X\}$ by a
circuit, we show that circuits for all its irreducible factors can be
computed in deterministic polynomial time.

\begin{itemize}
\item  Let $f(x_1,x_2,\ldots,x_n)\in\F\{X\}$ be a degree $d$ polynomial
  given by an arithmetic circuit of size $s$.  Then if $\F=\Q$, in
  deterministic $\poly(s,n,d)$ time we can output the circuits for the
  irreducible factors of $f$. If $\F$ is a finite field such that
  $char(\F)=p$, we obtain a deterministic $\poly(s,n,d,p)$ time
  algorithm for computing circuits for the irreducible factors of $f$.
\end{itemize}

\subsection*{Outline of the proofs}

\begin{itemize}
\item \textbf{Identity Testing Result:} The main ideas for our
  algorithm are based on the white-box Raz-Shpilka PIT algorithm for
  noncommutative ABPs \cite{RS05}. As in the Raz-Shpilka algorithm
  \cite{RS05}, if the circuit computes a nonzero polynomial $f \in
  \F\{X\}$, then our algorithm output a \emph{certificate monomial}
  $m$ such that coefficient of $m$ in $f$ is nonzero.

  We first sketch the main steps of the Raz-Shpilka algorithm. The
  Raz-Shpilka algorithm processes the input ABP (assumed homogeneous)
  layer by layer. Suppose layer $i$ of the ABP has $w$ nodes. The
  algorithm maintains a spanning set $\mathbb{B}_i$ of at most $w$
  many linearly independent $w$-dimensional vectors of monomial
  coefficients. More precisely, each vector $v_m\in\mathbb{B}_i$ is
  the vector of coefficients of monomial $m$ computed at each of the
  $w$ nodes in layer $i$. Furthermore, the coefficient vector at layer
  $i$ of any monomial is in the span of $\mathbb{B}_i$. The
  construction of $\mathbb{B}_{i+1}$ from $\mathbb{B}_i$ can be done
  efficiently.  Clearly the identity testing problem can be solved by
  checking if there is a nonzero vector in $\mathbb{B}_d$, where $d$
  is the total number of layers.

  Now we sketch our $\pit$ algorithm for polynomials over $\F\{\ex\}$
  given by circuits. Let $f$ be the input polynomial given by the
  circuit $C$.

  We encode monomials in the free nonassociative noncommutative ring
  $\F\{\ex\}$ as monomials in the free noncommutative ring
  $\F\angle{\ex,(,)}$, such that the encoding preserves the
  multiplication structure of $\F\{\ex\}$ (Observation \ref{obs1}).
  For $1\leq j\leq d$, we can efficiently find from $C$ a homogeneous
  circuit $C_j$ that computes the degree $j$ homogeneous part of $C$.
  Thus, it suffices to test if $C_j\equiv 0$ for each $j$. Hence, it
  suffices to consider the case when $f\in\F\{\ex\}$ is homogeneous
  and $C$ is a homogeneous circuit computing $f$.

  For $j\leq d$ let $G_j$ denote the set of degree $j$ gates of
  $C$. The algorithm maintains a set $\mathbb{B}_j$ of
  $|G_j|$-dimensional linearly independent vectors of monomial
  coefficients such that any degree $j$ monomial's coefficient vector
  is in the linear span of $\mathbb{B}_j$. Clearly, $|\mathbb{B}_j|\le
  |G_j|$. We compute $\mathbb{B}_{j+1}$ from the sets $\{\mathbb{B}_i
  : 1\leq i\leq j\}$. For each vector in $\mathbb{B}_j$ we also keep
  the corresponding monomial. In the nonassociative model a degree $d$
  monomial $m=(m_1 m_2)$ is generated in a \emph{unique way}. To check
  if the coefficient vector of $m$ is in the span of $\mathbb{B}_d$ it
  suffices to consider vectors in the spans of $\mathbb{B}_{d_1}$ and
  $\mathbb{B}_{d_2}$, where $d_1=\deg(m_1)$ and $d_2=\deg(m_2)$. This
  is a crucial difference from a general noncommutative circuit and
  using this property we can compute $\mathbb{B}_{j+1}$.

 \begin{comment}
 \begin{remark}
   We note that $+$ gates can add two different $\times$ gates with
   different left and right degrees. For example, it can add two
   $\times$ gates $u,v$ with children degree $(d_1,d_2)$ and
   $(d'_1,d'_2)$ respectively, where $d'_1+d'_2=d_1+d_2$ and $d_1 \neq
   d'_1$. Since $C$ is obtained by bracketing circuits over
   nonassociative free rings and such a bracketing preserves parse
   tree structure of each monomials, coefficient of monomials computed
   by these two $\times$ gates can not affect each other at any gate
   in $C$. This will be crucially used in the PIT algorithm. In other
   words, each monomial computed by $C$ has a unique parse tree (but
   number of parse trees in the circuit could be unbounded) and thus
   monomials computed at $u$ and $v$ are different.
 \end{remark}
 We note that these ideas do not work for general noncommutative
 circuits as each monomial can have many different parse tree
 structure in the circuit.
\end{comment}

 \item \textbf{Polynomial Factorization in $\F\{X\}$}

   For a polynomial $f\in\F\{\ex\}$, let $f_j$ denote the homogeneous
   degree $j$ part of $f$. For a monomial $m$, let $c_m(f)$ denote the
   coefficient of $m$ in $f$. We will use the $\pit$ algorithm as
   subroutine for the factoring algorithm. Arvind et al.\ \cite{AJR15}
   have shown that given a monomial $m$ and a homogeneous
   noncommutative circuit $C$, in deterministic polynomial time
   circuits for the formal left and right derivatives of $C$ with
   respect to $m$ can be efficiently computed. This result is another
   ingredient in our algorithm.

   We sketch the easy case, when the given polynomial $f$ of degree
   $d$ has no constant term. Applying our $\pit$ algorithm to the
   homogeneous circuit $C_d$ (computing $f_d$) we find a nonzero
   monomial $m=(m_1 ~m_2)$ of degree $d$ in $f_d$ along with its
   coefficient $c_m(f)$. Notice that for any nontrivial factorization
   $f=gh$, $m_1$ is a nonzero monomial in $g$ and $m_2$ is a nonzero
   monomial in $h$. Suppose $|m_1|=d_1$ and $|m_2|=d_2$. Then the left
   derivative of $C_d$ with respect to $m_1$ gives
   $c_{m_1}(g)~h_{d_2}$ and the right derivative of $C_d$ with respect
   to $m_2$ gives $c_{m_2}(h)~g_{d_1}$. We now use the circuits for
   these derivatives and the nonassociative structure, to find
   circuits for different homogeneous parts of $g$ and $h$. The
   details, including the general case when $f$ has a nonzero constant
   term, is in Section~\ref{sec:fact}.
\end{itemize}

\subsection*{Organization}
In Section \ref{prelim} we describe some useful properties of
nonassociative and noncommutative polynomials. In Section
\ref{sec:pit} we give the PIT algorithm for $\F\{X\}$. In Section
\ref{sec:fact} we describe the factorization algorithm for
$\F\{X\}$. Finally, we list some open problems in Section
\ref{conclusion}.

\section{Preliminaries}\label{prelim}

For an arithmetic circuit $C$, a \emph{parse tree} for a monomial $m$
is a multiplicative sub-circuit of $C$ rooted at the output gate
defined by the following process starting from the output gate:

\begin{itemize}
\item At each $+$ gate retain exactly one of its input gates.
\item At each $\times$ gate retain both its input gates.
\item Retain all inputs that are reached by this process.
\item The resulting subcircuit is multiplicative and computes a
  monomial $m$ (with some coefficient).
\end{itemize}

For arithmetic circuits $C$ computing polynomials in the free
nonassociative noncommutative ring $\F\{X\}$, the same definition for
the parse tree of a monomial applies. As explained in the
introduction, in this case each parse tree (generating some monomial)
comes with a bracketed structure for the multiplication. It is
convenient to consider a polynomial in $\F\{x_1,\ldots,x_n\}$ as an
element in the noncommutative ring $\F\angle{x_1,\ldots,x_n, (, )}$
where we introduce two auxiliary variables $($ and $)$ (for left and
right bracketing) to encode the parse tree structure of any
monomial. We illustrate the encoding by the following example.

Consider the monomial (which is essentially a binary tree with leaves
labeled by variables) in the nonassociative ring $\F\{x,y\}$ shown in
Figure \ref{fig1:sub1}. Its encoding as a bracketed string in the free
noncommutative ring $\F\angle{x,y,(,)}$ is $(( \ x \ y \ ) \ y \ )$
and its parse tree shown in Figure \ref{fig1:sub2}.

\begin{figure}[h]
\label{fig1}
\centering
\begin{subfigure}{.5\textwidth}
  \centering

  \begin{tikzpicture}[scale=0.75]
\node[circle,draw](z){$\times$}
  child{node[circle,draw]{ $\times$}  child{node[]{$x$}} child{node[]{$y$}}}
  child{
    node[]{$y$}};
\end{tikzpicture}
\caption{A nonassociative and noncommutative monomial $x y y$}
  \label{fig1:sub1}
\end{subfigure
\begin{subfigure}{.5\textwidth}
  \centering

 \begin{tikzpicture}[scale=0.75,sibling distance=3cm,
level 2/.style={sibling distance =2cm},
level 3/.style={sibling distance =1.6cm},
level 4/.style={sibling distance =1cm},
level 5/.style={sibling distance =.8cm}]
\node[circle,draw](z){\tiny $\times $}
child{node[circle,draw]{\tiny $\times$}
child{node[]{$($}}
child{node[circle,draw]{\tiny $\times$}
child{node[circle,draw]{\tiny $\times$}
child{node[]{$($}} child{node[]{$x$}} }
child{node[circle,draw]{\tiny $\times$}
child{node[]{$y$}} child{node[]{$)$}} }}}
child{node[circle,draw]{\tiny $\times$}
child{node[]{$y$}}
child{node[]{$)$}}} ;
\end{tikzpicture}
\caption{ Corresponding monomial $((xy)\ y)\in\F\angle{X}$.}
  \label{fig1:sub2}
\end{subfigure}
\caption{nonassociative \& noncommutative monomial and its corresponding noncommutative bracketed monomial}
\label{fig:test}
\end{figure}

Consider an arithmetic circuit $C$ computing a polynomial
$f\in\F\{X\}$. The circuit $C$ can be efficiently transformed to a
circuit $\tilde{C}$ that computes the corresponding polynomial
$\tilde{f}\in\F\angle{X, (, )}$ by simply introducing the bracketing
structure for each multiplication gate of $C$ in a bottom-up manner as
indicated in the following example figures. Consider the circuits
described in Figures \ref{fig2:sub1} and \ref{fig2:sub2} where
$f_i,g_i,h_i$'s are polynomials computed by subcircuits. Clearly the
bracket variables preserve the parse tree structure. The following
fact is immediate.

\begin{figure}[h]
\label{fig2}
\centering
\begin{subfigure}{.5\textwidth}
  \centering

  \begin{tikzpicture}[sibling distance=1.75cm, level 2/.style={sibling distance =0.75cm}]
\node[circle,draw](z){\small $+$}
 child{node[circle,draw]{\small $\times$} child{node[]{$f_1$}} child{node[]{$f_2$}} }
 child{node[circle,draw]{\small $\times$} child{node[]{$g_1$}} child{node[]{$g_2$}} }
 child{node[circle,draw]{\small $\times$} child{node[]{$h_1$}} child{node[]{$h_2$}} };
\end{tikzpicture}
\caption{ $C$ computing a nonassociative, \\ noncommutative polynomial.}
  \label{fig2:sub1}
\end{subfigure
\begin{subfigure}{.5\textwidth}
  \centering

  \begin{tikzpicture}[sibling distance=2.75cm, level 2/.style={sibling distance =1.25cm}, level 3/.style={sibling distance =.65cm}]
\node[circle,draw](z){\small $+$}

 child{node[circle,draw]{\small $\times$} child{node[circle,draw]{\small $\times$} child{node[]{$($}} child{node[]{$f_1$}}} child{node[circle,draw]{\small $\times$} child{node[]{$f_2$} } child{node[]{$)$} }    }}
 child{node[circle,draw]{\small $\times$} child{node[circle,draw]{\small $\times$} child{node[]{$($}} child{node[]{$g_1$}}} child{node[circle,draw]{\small $\times$} child{node[]{$g_2$} } child{node[]{$)$} }    }}
 child{node[circle,draw]{\small $\times$} child{node[circle,draw]{\small $\times$} child{node[]{$($}} child{node[]{$h_1$}}} child{node[circle,draw]{\small $\times$} child{node[]{$h_2$} } child{node[]{$)$} }    }}
 ;
\end{tikzpicture}
\caption{ $\tilde{C}$ that computes the corresponding noncommutative polynomial.}
  \label{fig2:sub2}
\end{subfigure}
\caption{Nonassociative circuit and its corresponding noncommutative bracketed circuit}
\label{fig:test}
\end{figure}

\begin{comment}

\begin{figure}[h]\label{fig12}
\centering
\begin{tikzpicture}[sibling distance=1.75cm, level 2/.style={sibling distance =0.75cm}]
\node[circle,draw](z){\small $+$}
 child{node[circle,draw]{\small $\times$} child{node[]{$f_1$}} child{node[]{$f_2$}} }
 child{node[circle,draw]{\small $\times$} child{node[]{$g_1$}} child{node[]{$g_2$}} }
 child{node[circle,draw]{\small $\times$} child{node[]{$h_1$}} child{node[]{$h_2$}} };
\end{tikzpicture}
\caption{ $C_{na}$ computing a non associative, non commutative polynomial.}
\end{figure}

\begin{figure}[h]\label{fig13}
\centering
\begin{tikzpicture}[sibling distance=3.75cm, level 2/.style={sibling distance =1.75cm}, level 3/.style={sibling distance =1cm}]
\node[circle,draw](z){\small $+$}

 child{node[circle,draw]{\small $\times$} child{node[circle,draw]{\small $\times$} child{node[]{$(_{\ell}$}} child{node[]{$f_1$}}} child{node[circle,draw]{\small $\times$} child{node[]{$f_2$} } child{node[]{$)_r$} }    }}
 child{node[circle,draw]{\small $\times$} child{node[circle,draw]{\small $\times$} child{node[]{$(_{\ell}$}} child{node[]{$g_1$}}} child{node[circle,draw]{\small $\times$} child{node[]{$g_2$} } child{node[]{$)_r$} }    }}
 child{node[circle,draw]{\small $\times$} child{node[circle,draw]{\small $\times$} child{node[]{$(_{\ell}$}} child{node[]{$h_1$}}} child{node[circle,draw]{\small $\times$} child{node[]{$h_2$} } child{node[]{$)_r$} }    }}
 ;
\end{tikzpicture}
\caption{ $C_{nc}$ computing the non commutative polynomial corresponding $C_{na}$.}
\end{figure}
\end{comment}

\begin{obs}\label{obs1}
A nonassociative noncommutative circuit $C$ computes a nonzero
polynomial $f\in\F\{X\}$ if and only if the corresponding
noncommutative circuit $\tilde{C}$ computes a nonzero polynomial
$\tilde{f}\in\F\angle{X,(, )}$.
\end{obs}

We recall that the free noncommutative ring $\F\angle{\ex}$ is not a
unique factorization domain (UFD) \cite{Cohn} as shown by the
following standard example : $x y x + x = x (y x + 1) = (x y + 1)
x$. In contrast, the nonassociative free ring $\F\{\ex\}$ is a
UFD.

\begin{proposition}\label{ufd}
  Over any field $\F$, the ring $\F\{\ex\}$ is a unique factorization
  domain. More precisely, any polynomial $f\in\F\{X\}$ can be
  expressed a product $f=g_1g_2\cdots g_r$ of irreducible polynomials
  $g_i\in\F\{X\}$. The factorization is unique upto constant factors
  and reordering.
\end{proposition}

\begin{remark}
Usually, even the ordering of the irreducible factors in the
factorization is unique. Exceptions arise because of the equality
$(g+\alpha)(g+\beta)=(g+\beta)(g+\alpha)$ for any polynomial
$g\in\F\{X\}$ and $\alpha,\beta\in\F$.
\end{remark}

We shall indirectly see a proof of this proposition in
Section~\ref{sec:fact} where we describe the algorithm for computing
all irreducible factors.

Given a noncommutative circuit $C$ computing a homogeneous polynomial
in $\F\angle{\ex}$ and a monomial $m$ over $\ex$, one can talk of the
left and right derivatives of $C$ w.r.t $m$ \cite{AJR15}. Let
$f=\sum_{m'}c_{m'}(f) m'$ for some $f\in\F\angle{\ex}$ and $A$ be the
subset of monomials $m'$ of $f$ that have $m$ as prefix. Then the left
derivative of $f$ w.r.t.\ $m$ is
\[
\frac{\partial^{\ell}f}{\partial m}=\sum_{m'\in A} c_{m'}(f) m'',
\]
where $m'=m\cdot m''$ for $m'\in A$. Similarly we can define the right
derivative $\frac{\partial^{r}f}{\partial m}$. As shown in
\cite{AJR15}, if $f$ is given by a circuit $C$ then in deterministic
polynomial time we can compute circuits for
$\frac{\partial^{\ell}f}{\partial m}$ and
$\frac{\partial^{r}f}{\partial m}$. We briefly discuss this in the
following lemma.

\begin{lemma}{\rm\cite{AJR15}}\label{derivative}
  Given a noncommutative circuit $C$ of size $s$ computing a
  homogeneous polynomial $f$ of degree $d$ in $\F\angle{\ex}$ and
  monomial $m$, there is a deterministic $\poly(n,d,s)$ time algorithm
  that computes circuits $C_{m,\ell}$ and $C_{m,r}$ for the left and
  right derivatives $\frac{\partial^\ell C}{\partial m}$ and
  $\frac{\partial^r C}{\partial m}$, respectively.
\end{lemma}

\begin{proof}
  We explain only the left partial derivative case. Let $m$ be a
  degree $d'$ monomial and $f\in\F\angle{X}$ be a homogeneous degree
  $d$ polynomial $f$ computed by circuit $C$. In \cite{AJR15},a small
  substitution deterministic finite automaton $A$ with $d'+2$ states
  is constructed that recognizes all length $d$ strings with prefix
  $m$ and substitutes 1 for prefix $m$. The transition matrices of
  this automaton can be represented by $(d'+2)\times(d'+2)$
  matrices. From the evaluation of circuit $C$ on these transition
  matrices will recover the circuit for $\frac{\partial^\ell
    C}{\partial m}$ in the $(1,d^{'} + 1)^{th}$ entry of the output
  matrix.
\end{proof}

The left and right partial derivatives of inhomogeneous polynomials
are similarly defined. The same matrix substitution works for
non-homogeneous polynomials as well \cite{AJR15}. As discussed above,
given a nonassociative arithmetic circuit $C$ computing a polynomial
$f\in\F\{\ex\}$, we can transform $C$ into a noncommutative circuit
$\tilde{C}$ that computes a polynomial $\tilde{f}\in\F\angle{X,(,)}$.
Suppose we want to compute the left partial derivative of $f$
w.r.t.\ a monomial $m\in\F\{X\}$. Using the tree structure of $m$ we
transform it into a monomial $\tilde{m}\in \F\angle{X,(,)}$ and then
we can apply Lemma~\ref{derivative} to $\tilde{C}$ and $\tilde{m}$ to
compute the required left partial derivative. We can similarly compute
the right partial derivative. We use this in Section
\ref{sec:fact}.

We also note the following simple fact that the homogeneous parts of a
polynomial $f\in\F\{X\}$ given by a circuit $C$ can be computed
efficiently. We can apply the above transformation to obtain
circuit $\tilde{C}$ and use a standard lemma (see e.g., \cite{SY10})
to compute the homogeneous parts of $\tilde{C}$.

\begin{lemma}\label{hom}
  Given a noncommutative circuit $C$ of size $s$ computing a
  noncommutative polynomial $f$ of degree $d$ in $\F\angle{\ex,(,)}$,
  one can compute homogeneous circuits $C_j$ (where each gate computes
  a homogeneous polynomial) for $j^{th}$ homogeneous part $f_j$ of
  $f$, where $0\leq j\leq d$, deterministically in time
  $\poly(n,d,s)$.
\end{lemma}

\section{Identity Testing in $\F\{X\}$}\label{sec:pit}

In this section we describe our identity testing algorithm.

\begin{theorem}\label{thm-pit}
  Let $f(x_1,x_2,\ldots,x_n)\in\F\{X\}$ be a degree $d$ polynomial
  given by an arithmetic circuit of size $s$. Then in deterministic
  $\poly(s,n,d)$ time we can test if $f$ is an identically zero
  polynomial in $\F\{X\}$.
\end{theorem}

\begin{proof}
By Lemma \ref{hom} we can assume that the input is a homogeneous
nonassociative circuit $C$ computing some homogeneous degree $d$
polynomial in $\F\{X\}$ (i.e.\ every gate in $C$ computes a
homogeneous polynomial).  Also, all the $\times$ gates in $C$ have
fanin 2 and $+$ gates have unbounded fanin. We can assume the output
gate is a $+$ gate. We can also assume w.l.o.g.\ that the $+$ and
$\times$ gates alternate in each input gate to output gate path in the
circuit (otherwise we introduce sum gates with fan-in 1).

The $j^{th}$-layer of circuit $C$ to be the set of all $+$ gates in
computing degree $j$ homogeneous polynomials. Let $s^{+}$ be the total
number of $+$ gates in $C$. To each monomial $m$ we can associate a
vector $v_m\in\F^{s^{+}}$ of coefficients, where $v_m$ is indexed by
the $+$ gates in $C$, and $v_m[g]$ is the coefficient of monomial $m$
in the polynomial computed at the $+$ gate $g$. We can also write
\[
v_m[g] = c_m(p_g),
\]
where $p_g$ is the polynomial computed at the sum gate $g$.

For the $j^{th}$ layer of $+$ gates, we will maintain a maximal
linearly independent set $\mathbb{B}_j$ of vectors $v_m$ of monomials.
These vectors correspond to degree $j$ monomials. Although
$v_m\in\F^{s^{+}}$, notice that $v_m[g]=0$ at all $+$ gates that do
not compute a degree $j$ polynomial. Thus, $|\mathbb{B_j}|$ is bounded
by the number of $+$ gates in the $j^{th}$ layer. Hence,
$|\mathbb{B_j}|\le s$.

The sets $\mathbb{B}_j$ are computed inductively for increasing values
of $j$. For the base case, the set $\mathbb{B}_1$ can be easily
constructed by direct computation.  Inductively, suppose the sets
$\mathbb{B}_i : 1\leq i\leq j-1$ are already constructed. We describe
the construction of $\mathbb{B}_j$. Computing $\mathbb{B}_d$ and checking
if there is a nonzero vector in it yields the identity testing algorithm.

We now describe the construction for the $j^{th}$ layer assuming we
have basis $\B_{j'}$ for every $j' < j$. Consider a $\times$ gate with
its children computing homogeneous polynomials of degree $d_1$ and
$d_2$ respectively. Notice that $j=d_1 + d_2$ and $0 < d_1 , d_2 <
j$. Consider the monomial\footnote{We note that the nonassociative
  monomial $m_1 m_2$ is a binary tree with the root having two
  children: the left child is the root of the binary tree for $m_1$
  and the right child is the root of the binary tree for $m_2$.} set

\[
M =\{ m_1 m_2 \ | \ v_{m_1} \in \mathbb{B}_{d_1} \text{ and } v_{m_2}
\in \mathbb{B}_{d_2} \}.
\]

We construct vectors $\{v_{m} \ | \ m \in M \}$ as follows.

\[
v_{m_1 m_2}[g] = \sum_{(g_{d_1}, g_{d_2})} v_{m_1}[g_{d_1}] v_{m_2}[g_{d_2}],
\]

where $g$ is a $+$ gate in the $j^{th}$ layer, $g_{d_1}$ is a $+$ gate
in the $d_1^{th}$ layer, $g_{d_2}$ is a $+$ gate in the $d_2^{th}$
layer, and there is a $\times$ gate which is input to $g$ and computes
the product of $g_{d_1}$ and $g_{d_2}$.

Let $\mathbb{B}_{d_1 , d_2}$ denote a maximal linearly independent
subset of $\{v_m \mid m \in M \}$.  Then we let $\mathbb{B}_d$ be a
maximal linearly independent subset of
\[
\bigcup_{ d_1 + d_2 = d}\mathbb{B}_{d_1 , d_2}.
\]

\begin{claim}
  For every monomial $m$ of degree $j$, $v_m$ is in the span of
  $\mathbb{B}_j$.
\end{claim}

\noindent\textit{Proof of Claim.}~~  Let $m=m_1 m_2$ and the degree of
$m_1$ is $d_1$ and the degree of $m_2$ is $d_2$ \footnote{Here a
  crucial point is that for a nonassociative monomial of degree $d$,
  such a choice for $d_1$ and $d_2$ is \emph{unique}. This is a place
  where a general noncommutative circuit behaves very differently.}.
By \emph{Induction Hypothesis} vectors $v_{m_1}$ and $v_{m_2}$ are in
the span of $\mathbb{B}_{d_1}$ and $\mathbb{B}_{d_2}$ respectively.
Hence, we can write
\[
v_{m_1} = \sum^{D_1}_{i=1} \alpha_i v_{m_i} \ \ v_{m_i} \in \mathbb{B}_{d_1}
\textrm{~~~and~~~}
v_{m_2} = \sum^{D_2}_{j=1} \beta_j v_{{m'}_j} \ \ v_{{m'}_j} \in
\mathbb{B}_{d_2},
\]
where $|\mathbb{B}_{d_j}|=D_j$. Now, for a gate $g$ in the $j^{th}$
layer, By Induction Hypothesis and by construction we have
 \begin{align*}
  v_{m}[g] &= \sum_{(g_{d_1} , g_{d_2})} v_{m_1}[g_{d_1}] v_{m_2}[g_{d_2}]
  = \sum_{g_{d_1} , g_{d_2}} (\sum^{D_1}_{i=1} \alpha_i v_{m_i}[g_{d_1}]) (\sum^{D_2}_{j=1} \beta_j v_{{m'}_j}[g_{d_2}])\\
  &= \sum^{D_1}_{i=1} \sum^{D_2}_{j=1} \alpha_i \beta_j \sum_{g_{d_1} , g_{d_2}} v_{m_i}[g_{d_1}] v_{{m'}_j}[g_{d_2}]
  = \sum^{D_1}_{i=1} \sum^{D_2}_{j=1} \alpha_i \beta_j v_{m_i {m'}_j}[g].
 \end{align*}

 Thus $v_m$ is in the span of $\mathbb{B}_{d_1 ,d_2}$ and hence in the
 span of $\mathbb{B}_j$. This proves the claim.

The PIT algorithm only has to check if $\mathbb{B}_d$ has a nonzero
vector. This proves the claim.

Suppose the input nonassociative circuit $C$ computing some degree $d$
polynomial $f\in\F\{X\}$ is inhomogeneous. Then, using Lemma \ref{hom}
we can first compute in polynomial time homogeneous circuits $C_j
~:~0\leq j\leq d$, where $C_j$ computes the degree-$j$ homogeneous
part $f_j$. Then we run the above algorithm on each $C_j$ to check
whether $f$ is identically zero. This completes the proof of the
theorem.
\end{proof}

\section{Polynomial Factorization in $\F\{X\}$}\label{sec:fact}

In this section we describe our polynomial-time white-box
factorization algorithm for polynomials in $\F\{X\}$. More precisely,
given as input a nonassociative circuit $C$ computing a polynomial
$f\in\F\{X\}$, the algorithm outputs circuits for all irreducible
factors of $f$. The algorithm uses as subroutine the PIT algorithm for
polynomial in $\F\{X\}$ described in Section~\ref{sec:pit}.

To facilitate exposition, we completely describe a deterministic
polynomial-time algorithm that computes a nontrivial factorization
$f=g\cdot h$ of $f$, by giving circuits for $g$ and $h$, unless $f$ is
irreducible. We will briefly outline how this extends to finding all
irreducible factors efficiently.

We start with a special case.

\begin{lemma}\label{lem2}
 Let $f\in\F\{\ex\}$ be a degree $d$ polynomial given by a circuit $C$
 of size $s$ such that the constant term in $f$ is zero. Furthermore,
 suppose there is a factorization $f=g\cdot h$ such that the constant
 terms in $g$ and $h$ are also zero. Then in deterministic
 $\poly(n,d,s)$ time we can compute the circuits for polynomials $g$
 and $h$.
\end{lemma}

\begin{proof}
We first consider the even more restricted case when $C$ computes a
homogeneous degree $d$ polynomial $f\in\F\{X\}$. For the purpose of
computing partial derivatives, it is convenient to transform $C$ into
the noncommutative circuit $\tilde{C}$, as explained in
Section~\ref{prelim}, which computes the fully bracketed polynomial
$\tilde{f}\in\F\angle{X,(,)}$. Using Theorem~\ref{thm-pit} we compute
a monomial $m=(m_1 m_2)$ where $m_1$ and $m_2$ are also fully
bracketed. We can transform $\tilde{C}$ to drop the outermost opening
and closing brackets. Now, using Lemma~\ref{derivative}, we compute
the resulting circuits left partial derivative w.r.t.\ $m_1$ and right
partial derivative w.r.t.\ $m_2$. Call these $\tilde{f}_1$ and
$\tilde{f}_2$. We can check if $\tilde{f}=(\tilde{f}_1 \tilde{f}_2)$:
we first recover the corresponding nonassociative circuits for $f_1$
and $f_2$ from the circuits for $\tilde{f}_1$ and $\tilde{f}_2$.  Then
we can apply the PIT algorithm of Theorem~\ref{thm-pit} to check if
$f=f_1 f_2$. Clearly, $f$ is irreducible iff $f\ne f_1
f_2$. Continuing thus, we can fully factorize $f$ into its
irreducible factors.

Now we prove the actual statement. Applying Lemma \ref{hom}, we
compute homogeneous circuits $C_j : 1\leq j\leq d$ for the homogeneous
degree $j$ component $f_j$ of the polynomial $f$.  Clearly $f_d =
g_{d_1} h_{d_2}$. We run the PIT algorithm of Theorem~\ref{thm-pit} on
the circuit $C_d$ to extract a monomial $m$ of degree $d$ along with
its coefficient $c_m(f_d)$ in $f_d$. Notice that the monomial $m$ is
of the form $m=(m_1~m_2)$. If $g$ and $h$ are nontrivial factors of
$f$ then $m_1$ and $m_2$ are monomials in $g$ and $h$
respectively. Compute the circuits for the left and right derivatives
with respect to $m_1$ and $m_2$.
\[
\frac{\partial^{\ell} C_d}{\partial m_{1}}  =  c_{m_1}(g_{d_1})
\cdot h_{d_2} \textrm{~~~and~~~}
\frac{\partial^{r} C_d}{\partial m_{2}}  =  c_{m_2}(h_{d_2})\cdot g_{d_1}.
\]

In general the $(i+ d_2)^{th} : i\leq d-d_2$ homogeneous part of $f$
can be expressed as
\[
 f_{i + d_2} = g_i h_{d_2} + \sum_{t=i+1}^{i+ d_2 - 1} g_t h_{{d_2} \ - \ (t - i)}.
\]
We depict the circuit $C_{i+d_2}$ for the polynomial $f_{i+d_2}$ in
Figure \ref{fig4}. The top gate of the circuit is a $+$ gate. From
$C_{i+d_2}$, we construct another circuit $C'_{i+d_2}$ keeping only
those $\times$ gates as children whose left degree is $i$ and right
degree is $d_2$. The resulting circuit is shown in Figure \ref{fig5}.
The circuit $C'_{i+d_2}$ must compute $g_i h_{d_2}$.  By taking the
right partial of $C'_{i+d_2}$ with respect to $m_2$, we obtain the
circuit for $c_{m_2}(h_{d_2})~ g_i$.

\tikzset{
itria/.style={
  draw,dashed,shape border uses incircle,
  isosceles triangle,shape border rotate=90,yshift=-1.45cm},
rtria/.style={
  draw,dashed,shape border uses incircle,
  isosceles triangle,isosceles triangle apex angle=90,
  shape border rotate=-45,yshift=0.2cm,xshift=0.5cm},
ritria/.style={
  draw,dashed,shape border uses incircle,
  isosceles triangle,isosceles triangle apex angle=110,
  shape border rotate=-55,yshift=0.1cm},
letria/.style={
  draw,dashed,shape border uses incircle,
  isosceles triangle,isosceles triangle apex angle=110,
  shape border rotate=235,yshift=0.1cm}
}

\begin{figure}[h]\label{fig2}
\centering
\begin{tikzpicture}[sibling distance=5cm, level 2/.style={sibling distance =2cm}]
\node[circle,draw](z){\small $+$}
  child{node[circle,draw]{\small $\times$}  child{node[ritria]{\small $i$}} child{node[letria]{\small $d_2$}}}

  child{node[circle,draw]{\small $\times$}  child{node[ritria]{\small $k$}} child{node[letria]{\small $l$}}}

  child{node[circle,draw]{\small $\times$}  child{node[ritria]{\small $i$}} child{node[letria]{\small $d_2$}}};
\end{tikzpicture}
\caption{Circuit $C_{i+d_2}$ for $f_{i+d_2}$}\label{fig4}
\end{figure}

\begin{figure}[h]\label{fig3}
\centering
\begin{tikzpicture}[sibling distance=5cm, level 2/.style={sibling distance =2cm}]
\node[circle,draw](z){\small $+$}
child{node[circle,draw]{\small $\times$} child{node[ritria]{\small $i$}}
  child{node[letria]{\small $d_2$}}}
child{node[circle,draw]{\small $\times$}
child{node[ritria]{\small $i$}} child{node[letria]{\small $d_2$}}};
\end{tikzpicture}
\caption{$C'_{i+d_2}$ keeps only degree $(i,d_2)$ type $\times$
gates.}\label{fig5}
\end{figure}

We repeat the above construction for each $i\in[d_1]$ to obtain
circuits for $c_{m_2}(h_{d_2}) g_{i}$ for $1 \leq i \leq
d_1$. Similarly we can get the circuits for $c_{m_1}(g_{d_1}) h_i$ for
each $i\in [d_2]$ using the left derivatives with respect to the
monomial $m_1$.

By adding the above circuits we get the circuits $C_g$ and $C_h$ for
$c_{m_2}(h_{d_2}) g$ and $c_{m_1}(g_{d_1}) h$ respectively.  We set
$C_g = \frac{c_{m_2}(h_{d_2})}{c_{m}(f)} g$ so that $C_g C_h =f$.
Using PIT algorithm one can easily check whether $g$ and $h$ are
nontrivial factors. In that case we further recurse on $g$ and $h$ to
obtain their irreducible factors.
\end{proof}

Now we consider the general case when $f$ and its factors $g, h$ have
arbitrary constant terms. In the subsequent proofs we assume, for
convenience, that $\deg(g)\geq \deg(h)$. The case when $\deg(g) <
\deg(h)$ can be handled analogously.  We first consider the case
$\deg(g)=\deg(h)$.

\begin{lemma}\label{lem3a}
  For a degree $d$ polynomial $f\in \F\{X\}$ given by a circuit $C$
  suppose $f=(g+\alpha)(h+\beta)$, where $g,h\in\F\{X\}$ such that
  $\deg(g)=\deg(h)$, and $\alpha,\beta\in\F$. Suppose $m=(m_1 m_2)$ is
  a nonzero degree $d$ monomial. Then, in deterministic polynomial
  time we can compute circuits for the polynomials $c_{m_1}(g)\cdot h$
  and $c_{m_2}(h)\cdot g$, where $c_{m_1}(g)$ and $c_{m_2}(h)$ are
  coefficient of $m_1$ and $m_2$ in $g$ and $h$ respectively.
\end{lemma}

\begin{proof}
  We can write $f=(g+\alpha)(h+\beta) = g\cdot h + \beta\cdot g +
  \alpha\cdot h + \alpha\cdot \beta$. Applying the PIT algorithm of
  Theorem~\ref{thm-pit} on $f$, we compute a maximum degree monomial
  $m=(m_1 m_2)$. Computing the left derivative of circuit $C$ w.r.t.\
  monomial $m_1$, after removing the outermost brackets, we obtain a
  circuit computing $c_{m_1}(g) h + \beta c_{m_1}(g) + \alpha
  c_{m_1}(h)$. Dropping the constant term, we obtain a circuit
  computing polynomial $c_{m_1}(g)h$.  Similarly, computing the right
  derivative w.r.t $m_2$ yields a circuit for $c_{m_2}(h) g + \beta
  c_{m_2}(g) + \alpha c_{m_2}(h)$. Removing the constant term we get a
  circuit for $c_{m_2}(h)g$.
\end{proof}

When $\deg(g) > \deg(h)$ we can recover $h+ \beta$ entirely (upto a
scalar factor) and we need to obtain the homogeneous parts of $g$
separately.

\begin{lemma}\label{lem3}
  Let $f=(g+ \alpha)\cdot (h+ \beta)$ be a polynomial of degree $d$ in
  $\F\{\ex\}$ given by a circuit $C$. Suppose $\deg(g) >
  \deg(h)$. Then, in deterministic polynomial time we can compute the
  circuit $C'$ for $c_{m_1}(g)(h+\beta)$.
\end{lemma}

\begin{proof}
  Again, applying the PIT algorithm to $f$ we obtain a nonzero degree
  $d$ monomial $m=(m_1~m_2)$ of $f$. If $f=(g+\alpha)(h+\beta)$ then
  $f=g\cdot h + \alpha h + \beta g + \alpha\beta$. As
  $\deg(g)>\deg(h)$, the left partial derivative of $C$ with respect
  to $m_1$ yields a circuit $C'$ for $c_{m_1}(g)~(h + \beta)$.
\end{proof}

Extracting the homogeneous components from the circuit $C'$ given by
Lemma~\ref{lem3}, yields circuits for $\{ c_{m_1}(g) h_i \ : \ i \in
[d_2] \}$. We also get the constant term $c_{m_1}(g) \beta$.  Now we
obtain the homogeneous components of $g$ as follows.

\begin{lemma}\label{lem4a}
  Suppose circuit $C$ computes $f$, where $f=(g+\alpha)~(h+\beta)$ of
  degree $d$, $\alpha,\beta\in\F$, $\deg(g)=d_1$ and $\deg(h)=d_2$
  such that $d_1 > d_2$.
\begin{itemize}
\item Let $m$ be a nonzero degree $d$ monomial of $f$ such that
  $m=(m_1~m_2)$. Then circuits for $\{ c_{m_2}(h) g_i : i \in [d_1 -
  d_2 +1, d_1] \}$ can be computed in deterministic polynomial time.

\item The $(d_2 + i)^{th}$ homogeneous part of $f$ is given by $f_{d_2
    + i}=\sum_{j=0}^{d_2-1}~g_{d_2 + i -j}~h_{j} + g_{i} ~h_{d_2}$ for
  $1\leq i\leq d_1 - d_2$.  From the circuit $C_{d_2 + i}$ of $f_{d_2
    + i}$, we can efficiently compute circuits for $\{ c_{m_2}
  (h_{d_2}) g_{i} : 1\leq i\leq d_1 - d_2\}$.
\end{itemize}

\end{lemma}

\begin{proof}
  For the first part, fix any $i\in[d_1-d_2+1, d_1]$, and compute the
  homogeneous $(i + d_2)^{th}$ part $f_{i+d_2}$ of $f$ by a circuit
  $C_{i + d_2}$. Similar to Lemma \ref{lem2}, we focus on the
  sub-circuits of $C_{i + d_2}$ formed by $\times$ gate of the degree
  type $(i, d_2)$. Since $i$ is at least $d_1 - d_2 + 1$, such gates
  can compute the multiplication of a degree $i$ polynomial with a
  degree $d_2$ polynomial.  Then, by taking the right partial
  derivative with respect to $m_2$ we recover the circuits for
  $c_{m_2}(h_{d_2}) ~g_i$ for any $i\in[d_1-d_2+1, d_1]$.

  Next, the goal is to recover the circuits for $g_i$ (upto a scalar
  multiple), where $1\leq i\leq d_1-d_2$, and also recover the
  constant terms $\alpha$ and $\beta$. When $i \leq d_1 - d_2$ a
  product gate of type $(i,d_2)$ can entirely come from $g$ which
  requires a different handling.

  We explain only the case when $i=d_1 - d_2$ (the others are
  similar). For $i=d_1-d_2$, we have $f_{d_1} = \beta g_{d_1} +
  \sum_{j=1}^{d_2-1}~g_{d_1 -j}~h_{j} + g_{d_1 - d_2} ~h_{d_2}$. By
  Lemma \ref{lem3}, we can compute a circuit $C'$ for $c_{m_1}(g) (h +
  \beta)$. Extracting the constant term yields $c_{m_1}(g)
  \beta$. From Lemma \ref{lem4a} we have a circuit $C''$ for
  $c_{m_2}(h) g_{d_1}$. Multiplying these circuits, we obtain a
  circuit $C^*$ for $c_{m_2}(h)c_{m_1}(g)\beta g_{d_1}$.  Since
  $c_{m_2}(h)c_{m_1}(g) = c_{m}(f)$, dividing $C^*$ by $c_m (f)$
  yields a circuit for $\beta g_{d_1}$. Note that, by the first part
  of this lemma, we already have circuits for every term $g_{d_1-j}$
  appearing in the above sum. Subtracting $\beta g_{d_1} +
  \sum_{j=1}^{d_2-1}~g_{d_1 -j}~h_{j}$ from the circuit $C_{d_1}$ for
  $f_{d_1}$, yields a circuit for polynomial $g_{d_1 - d_2} h_{d_2}$.
  Computing the right derivative of the resulting circuit w.r.t $m_2$
  (Lemma~\ref{derivative}) yields a circuit for $c_{m_2}(h) g_{d_1 -
    d_2}$.

  For general $i\le d_1-d_2$, when we need to compute $g_i$, again we
  will have already computed circuits for all $g_j, j>i$. A suitable
  right derivative computation will yield a circuit for $c_{m_2}(h)
  g_{i}$.
\end{proof}

Lemmas \ref{lem2}, \ref{lem3a}, \ref{lem3}, and \ref{lem4a} yield an
efficient algorithm for computing circuits for the two factors
$c_{m_2}(h)(\sum_{i=1}^{d_1} g_i)$ and $c_{m_1}(g) (\sum_{i=1}^{d_2}
h_i)$ when $\deg(g) \ge \deg(h)$. The case when $\deg(g) < \deg(h)$ is
similarly handled using left partial derivatives in the above lemmas.

Now we explain how to compute the constant terms of the individual
factors. We discuss the case when $\alpha\ne 0$. The other case is
similar.

First we recall that given a monomial $m$ and a noncommutative circuit
$C$, the coefficient of $m$ in $C$ can be computed in deterministic
polynomial time \cite{AMS10}.  We know that $f_0 = \alpha\cdot \beta$.
We compute the coefficient of the monomial $m_1$ in the circuits for
polynomials $c_{m_2}(h)c_{m_1}(g) g h$, $c_{m_2}(h) g$, and
$c_{m_1}(g)h$. Let these coefficients be $a, b$ and $c$,
respectively. Moreover, we know that $c_{m_2}(h)c_{m_1}(g)$ is the
coefficient of monomial $m=(m_1 ~m_2)$ in $f$. Let the coefficient of
$m_1$ in $f$ be $\gamma$. Let $\gamma_1=c_{m_1}(g)$ and
$\gamma_2=c_{m_2}(h)$ and $\delta=c_{m_1}(g)c_{m_2}(h)$.

Now equating the coefficient of $m_1$ from both side of the equation
$f = (g + \alpha) (h + \beta)$ and substituting
$\beta=\frac{f_0}{\alpha}$, we get
\[
\gamma = \frac{a}{\gamma_1\gamma_2} + \frac{\alpha c}{\gamma_1} +
\frac{f_0 b}{\alpha \gamma_2} =  \frac{a}{\delta} + \frac{\alpha c}{\gamma_1} +
\frac{f_0 b}{\alpha \gamma_2}.
\]

Letting $\xi=\alpha \gamma_2$, this gives a quadratic equation in
the unknown $\xi$.
\[
c\xi^2 + (a - \gamma \delta)\xi + f_0 b\delta = 0.
\]

By solving the above quadratic equation we get two solutions $A_1$ and
$A_2$ for $\xi=\alpha\gamma_2$. Notice that $\beta\gamma_1 =
\frac{\delta f_0}{\xi}$. As we have circuits for $c_{m_2}(h) g=
\gamma_2 g$ and for $c_{m_1}(g) h= \gamma_1 h$, we obtain circuits for
$\gamma_2(g+\alpha)$ and $\gamma_1(h+\beta)$ (two solutions,
corresponding to $A_1$ and $A_2$). To pick the right solution, we can
run the $\pit$ algorithm to check if $\gamma_1\gamma_2 f$ equals the
product of these two circuits that purportedly compute
$\gamma_2(g+\alpha)$ and $\gamma_1(h+\beta)$.

Over $\Q$ we can just solve the quadratic equation in deterministic
polynomial time using standard method. If $\F=\F_q$ for $q=p^r$, we
can factorize the quadratic equation in deterministic time
$\poly(p,r)$ \cite{GS92}. Using randomness, one can solve this problem
in time $\poly(\log p,r)$ using Berlekamp's factoring algorithm
\cite{Ber71}. This also completes the proof of the following.

\begin{theorem}\label{thm-fact1}
Let $f\in\F\{X\}$ be a degree $d$ polynomial given by a circuit of
size $s$. If $\F=\Q$, in deterministic $\poly(s,n,d)$ time we can
compute a nontrivial factorization of $f$ or reports $f$ is
irreducible. If $\F$ is a finite field such that $char(\F)=p$, we
obtain a deterministic $\poly(s,n,d,p)$ time algorithm that computes a
nontrivial factorization of $f$ or reports $f$ is irreducible.
\end{theorem}

Finally, we state the main result of this paper.

\begin{theorem}\label{thm-fact2}
  Let $f\in\F\{X\}$ be a degree $d$ polynomial given by a circuit of
  size $s$. Then if $\F=\Q$, in deterministic $\poly(s,n,d)$ time we
  can output the circuits for the irreducible factors of $f$. If $\F$
  is a finite field such that $char(\F)=p$, we obtain a deterministic
  $\poly(s,n,d,p)$ time algorithm for computing circuits for the
  irreducible factors of $f$.
\end{theorem}

\begin{remark}
We could apply Theorem~\ref{thm-fact1} repeatedly to find all
irreducible factors of the input $f\in\F\{X\}$. However, the problem
with that approach is that the circuits for $g$ and $h$ we computed in
the proof of Theorem~\ref{thm-fact1}, where $f=gh$ is the
factorization, is larger than the input circuit $C$ for $f$ by a
polynomial factor. Thus, repeated application would incur a
superpolynomial blow-up in circuit size. We can avoid that by
computing the required partial derivative of $g$ as a suitable partial
derivative of the circuit $C$ directly. This will keep the circuits
polynomially bounded. This idea is from \cite{AJR15} where it is used
for homogeneous noncommutative polynomial factorization. Combined
with Theorem~\ref{thm-fact1} this gives the polynomial-time algorithm
of Theorem~\ref{thm-fact2}.
\end{remark}

\section{Conclusion}\label{conclusion}

Motivated by the nonassociative circuit lower bound result shown in
\cite{HWY10b}, we study PIT and polynomial factorization in the free
nonassociative noncommutative ring $\F\{X\}$ and obtain efficient
white-box algorithms for the problems.

Hrubes, Wigderson, and Yehudayoff \cite{HWY10b} have also shown
exponential circuit-size lower bounds for nonassociative, commutative
circuits. It would be interesting to obtain an efficient polynomial
identity testing algorithm for that circuit model too. Even a
randomized polynomial-time algorithm is not known.

Obtaining an efficient \emph{black-box} PIT in the ring $\F\{X\}$ is
also an interesting problem. Of course, for such an algorithm the
black-box can be evaluated on a suitable nonassociative algebra. To
the best of our knowledge, there seems to be no algorithmically useful
analogue of the Amitsur-Levitzki theorem \cite{AL50}.

redpajama_set_name: RedPajamaArXiv


Bought this hand cream, which promised advertising promised to soften the cuticles. Well, naturally, thanks to the almond oil. Also advertising promised that the cream is quickly absorbed. As we understand, the no absolutely. Hands greasy. There only after the cream to wipe them. Dissatisfied with the purchase absolutely.
Hand Cream "One hundred recipes for beauty" diet and restoring (beeswax, creamy yogurt and carrot juice) - Fat!
Hand and nail complex "Velvet Hands" did not give damaged skin.
In the summer a month cut off day for the repair of water piping. To buy bottled drinking water, and had to wash one.


Arvena Thelas is a Dunmer commoner living in Anvil. Word on the streets suggests that Arvena keeps strange things in her basement, but according to Arvena, there's nothing strange about the four rats she keeps as house pets. Regardless, one of her neighbors is bothered by the mere thought of living next door to a bunch of rats and during the related quest, you'll have to sort things out.
She's known around town as "the rat lady," but Arvena chooses to ignore that and actually spends several hours socializing with her fellow townsfolk. She gets out of bed every morning at 6am and spends two hours in the house before leaving for breakfast at The Count's Arms. At 10am, she heads for the shady bench underneath the big oak near the Anvil Dock Gate. Once seated, she reads the book Biography of Barenziah, v 2 until 4pm when she returns home. At 6pm, she once again enters The Count's Arms, unknowingly eating her dinner alongside the very person responsible for her rat problem. She heads back to the house at 8pm and wanders around there until it's time to go to bed at 10pm. On rainy days, she will skip reading on the bench and head straight back to her house. During the related quest, she will cancel all appointments and just stroll around on the second floor of her house, eagerly awaiting news from you.
She wears a set of common middle-class clothing, including a burgundy linen shirt, a pair of burgundy linens, and pigskin shoes. She carries her copy of Biography of Barenziah, v 2, her house key, and a leveled amount of gold.
The very first time you approach her, she will politely introduce herself: "I'm Arvena Thelas. They call me 'the rat lady' on account of all my pet rats." If you ask her about Anvil, she will reflect on the increasing amount of rumors around town: "You can't imagine the fuss some people make. My rats are no problem for anyone."
At Azzan's request you'll have to find Arvena right away, and when you do so, she will fill you in on her special relationship with her unusual house pets: "Ah... you must be from the Fighters Guild. Good. I have a problem, it has to do with the rats my basement. That's right. Rats. In my basement. And something has been killing them! It's horrible. My poor babies! You must do something! I don't know what I'd do without them. Their little pink noses, their scaly little tails. Please, get to the basement and find out what's happening." Speaking to her again before dealing with the problems in the basement will have her say "Aren't you going to take care of this? What am I paying you for?"
After investigating the basement and discovering the mountain lions, reporting back to her will have her greet you with "Well, what have you found? Did you take care of my babies? What was going on down there?" After informing her that mountain lions are in her basement she will say "A mountain lion? In my basement? But... how? That's not possible. But, it happened! What if there are more? What if it wasn't alone? Where there's one, there will be more. Find Pinarus Inventius. He's a hunter, and knows this area inside and out. He'll know what to do." Speaking to her again will have her greet you with the line "You should be looking for Pinarus! What are you doing here?"
At the end of the quest, the person responsible for the whole mess with the mountain lions will make you an offer: either tell Arvena about her, or don't. If you choose to tell Arvena the truth, she will give you a lesson in Speechcraft and say: "I knew it! That s'wit! Oh, I'll get her. You just wait! Must have taken some fast talking to get her to confess! Maybe I can teach you a little bit more about how to talk to people. And, of course, here's the payment for the contract. Thank you." If you choose not to tell her the truth, you'll receive only the gold reward as well as the following dialogue: "She didn't, huh? Hmph. But, you've taken care of the problem, and I suppose that's what counts. Thanks for that. Here's your payment." Also, if all of her rats die during the quest, she will not hesitate to cancel the contract: "My rats are all dead! It's too late to do any more. I won't be needing your services any longer." After this, she will greet you contemptuously: "Useless Fighters Guild. What do you want?" If you succeed with the quest, she will greet you in a totally different manner: "Thank you for all your help. My rats appreciate it."
Other people will share rumors about her: "Arvena Thelas is an odd one. I've heard some strange noises coming from her basement." and "Something about Arvena Thelas is a bit odd. I've heard she keeps strange things in her basement." Others will say: "That woman is a bit off-kilter. I don't even want to know what she's got in her basement." and "She's a nut. Whatever's going on in that house, I don't want to know about it." During the quest, Pinarus Inventius will reveal that he shares the public opinion: "A hunt will do us good, and maybe make that old nut feel better."
This page was last modified on 17 June 2018, at 11:49.


I adore chia seed pudding. It's a super easy way to make a delicious snack or breakfast on the go.
A traditional chia seed pudding is made with about 1/3 cup of chia seeds, 1 1/2 cups of milk, a sweetener, and fruit. I love to make it with fresh almond milk or coconut milk and I think it's fun to layer it with yogurt. The possibilities are endless when it comes to making chia seed pudding, just use your imagination!
I know the texture takes a little getting used to, but I've got a simple trick to get around that. To create a more creamy pudding texture, blend all the ingredients together in blender or Vitamix before letting it set in the fridge.
Why are eat chia seeds healthy? Chia seeds are well known for containing healthy omega 3 fats. They also provide a healthy dose of protein, fiber, and important minerals like calcium, magnesium, and iron. These amazing little seeds also have great absorptive power! They can absorb up to ten times their weight in water, helping you to stay full and satisfied.
This is one of my favorite chia seed pudding recipes. I love the layering of yogurt in between the chia and the crumb topping is the bomb!
EA over at The Spicy RD, knows how to make a fun chia seed pudding. This one is infused with matcha green tea and topped with fresh mango. YUM!
Stephanie over at Hello Natural shows you how to make a warm apple cinnamon chia pudding. Gorgeous and perfect for fall!
Megan over at With Salt and Wit makes a low calorie PB + chocolate chia seed pudding, using cottage cheese and PB2. Pretty creative if you ask me!
Rachael at An Avocado a Day makes this delicious breakfast chia pudding with mashed banana, almonds and a dollop of jam. The perfect way to start the day!
This mouthwatering chia seed pudding with pineapple from Honestly Yum just makes me happy looking at it. Come on, you know you want to eat this right now!
Abby of Langer Nutrition created this simple chia seed pudding and topped it with a handful of ruby red raspberries. This pudding is just asking to get scarfed up for breakfast tomorrow!
Love ALL these chia pudding recipes Danielle! Thanks so much for including my Ginger Matcha Chia Pudding 🙂 Love your idea to blend the ingredient before chilling-will try that next time I make a batch. Hope you're having a wonderful weekend!


In my effort of moving away form Gmail, I took the opportunity to set up my new email account in such a way that I could better organize my work on GitHub.
There's a feature that GitHub has never had and that I'd find very useful, workspaces. I used to look at the notifications to know the things I should focus on. If you are part of multiple organizations, all those notifications show up in the same place. As a result, when I open the notifications page to plan the open source work, I end up looking at work stuff and the other way around.
Luckily, most email providers offer defining rules for emails. With rules, you can match certain emails that you receive, and define an action for them, for example archiving or deleting.
Configure the notifications per organization and forward them to the right email account.
Create a folder per workspace. In my case it was "shopify", "work", and "tuist".
Define a rule where you match the recepient with the emails above and send the email to the right folder.
Simple, isn't it? With this little tweak I can access a notifications-free GitHub, focus on my work, and check the notifications on my email when I need to plan the work.


The UNP politburo will meet today at Temple Trees to discuss the methodology to be followed when electing the main officer bearers and the names of those to be selected to these posts, a politburo member said.
It was reported that there was a suggestion during the previous meeting that the three key posts General Secretary, National Organizer and the Chairman should be decided through a ballot.
However other sources said there was another proposal that the general secretary and other posts should be appointed in the usual way and the party leader should also have a say in it.


Mr Pete Wishart MP, Member of Parliament for Perth & North Perthshire helped to mark the Federation of Small Business's Small Business Saturday by visiting a number of local businesses in his constituency at the weekend.
Mr Wishart was accompanied by Nicola Martin, Chair of Perthshire Businesswomen's Network and the inspiration behind the #PerthLoveFest campaign to encourage the people of Perth to rekindle their passion for all of our wonderful independent retailers, restaurants, pubs, producers and events.
"Small businesses, like those I visited on Small Business Saturday are the heartblood of the local economy and I am delighted to be able to lend my support to this excellent campaign to put the spotlight on the important role that they play and the need for us all to support them.
"Money spent in small local businesses stays in the local economy and so we all benefit in the long run. With just a couple of short shopping weeks left before Christmas, what better time could there be than this to show our support for these important local economic engines?
"The aim of Small Business Saturday is to support, inspire and promote small businesses and this is something our #PerthLoveFest campaign aims to do all year round.
"I am really pleased to be able to join Pete in helping to highlight them importance of independent retailers and small businesses and showing what they can bring to the mix in a city such as Perth.


The Cruiser room is designed for children who are crawling and learning to walk. Separated into two areas- one for sleeping and eating and another for activities. On the activity side, the floor is padded for safety as children have discovered their new abilities.
Like the infant room, we follow your child's eating and sleeping schedule. As your child gets older, they gradually wean from bottles, are introduced to table food, and transition to sleeping on mats in preparation for the Toddler room. All transitions are gradual and as stress-free as possible.
We begin basic circle time with fun activities that engage the senses and develop gross and fine motor skills. Story time includes Bible stories, music, arts and crafts, and sign language. Daily sheets are also sent home each day to report your child's activities. We continue to maintain better teacher to child ratios of 1:3 or better most of the time rather than 1:5.


* @param int $network_id Network ID. Corresponds to site_id in the sitemeta table.
* @return array|string Array if $single is false. Value of the meta data field if $single is true.
/** Add a metadata field to a network.
* @param string $key Metadata name.
* @param mixed $value Metadata value. Must be serializable if non-scalar.
* @param bool $unique Optional. Default is false. Whether the same key should be added.
* @return bool|int Meta ID on success. False on failure.
* Update network meta field based on network ID.
* @param string $key Key of metadata to be updated.
* @return bool True on success. False on failure.
* Remove specified metadata from a network.
* @param string $key Key of metadata to be deleted.
* @param mixed $value Optional. Metadata value. Must be serializable if non-scalar.


text:
Home Hospitality & Tourism Construction Set To Start On Kampot Tourism Seaport
Construction Set To Start On Kampot Tourism Seaport
Passenger ferries coast along the Kampong Bay river in Kampot at sunset, with Bokor mountain in the background.
Construction of the first seaport for tourist vessels in Kampot province is due to start in September.
Provincial tourism department director Soy Sinol said a construction study of the Asian Development Bank-funded project had been completed. The $18-million tourism seaport is due to come into service by 2019.
Sinol said it would boost tourism in the province by connecting seaborne tourists from Vietnam, Preah Sihanoukville province and Thailand. "This is an international tourism seaport in Kampot to connect Cambodia to Koh Tral island [Vietnam's Phu Quc island] island and from Koh Tral island to here and to neighbouring countries," he said.
The development of the seaport is important in attracting tourists by sea to Cambodia's coastal areas, he said, adding that the seaport in Tek Chhou district is 300 metres long, allowing ships with 200 to 300 passengers to use it.
The ADB approved the loan in 2014 and said the seaport and other infrastructure in southern Cambodia would open up new opportunities for tourism beyond popular destinations such as the Angkor temples. An ADB report on tourism in the Greater Mekong sub-region says the seaport is expected to service 360,000 international and domestic tourists when it opens, and 442,900 by 2020.
Ho Vandy, secretary-general of the Cambodia National Tourism Alliance, said the seaport would help promote tourism in coastal areas, and he urged the government to go into a partnership with the private sector to develop it.
"Public-private partnership needs to be strengthened in Cambodia's tourism sector. This Kampot tourism seaport project is an excellent opportunity for that," said Vandy. Last year, Kampot province welcomed about 900,000 foreign tourists, of which Vietnamese tourists topped the list.
Previous articleGround Broken For Cambodia's First Oil Refinery
Next articleInsurance Giant AIA Enters The Cambodian Market
Foreign Tourist Arrivals In Cambodia Up Over 12 Percent
Eco-tourism Legislation In The Pipeline.
Tourism Minister Pushes Siem Reap To Clean Up
Construction Gets Underway On Hyatt Regency Phnom Penh Hotel
Tourism Revenue Up 20 Percent
Chinese Firm Plans Hotels Boost In Cambodia

redpajama_set_name: RedPajamaCommonCrawl


How does Bunnings' in-home installation work?
Purchase an exhaust or heat lamp at Bunnings and pick up an installation card. Installation can be organised online at Services or at the Special Orders desk.
How do I use my installation card?
Follow the instructions on the exhaust and heat lamp installation card to arrange installation or visit Services to book your installation.
Where do I find an installation card?
Installation cards are located in the electrical aisle or at the Special Orders desk in-store.
Do I have to buy an exhaust or heat lamp from Bunnings?
Yes, installation is provided as an additional service to install an exhaust or heat lamp from our wide range.
What is Bunnings' relationship with hipages?
Bunnings has partnered with hipages to provide our customers with this handy exhaust and heat lamp installation service.
You can speak to any team member at the Special Orders desk or your in-store electrical expert.
What is the time between purchase and installation?
After you have purchased your exhaust or heat lamp and installation you can arrange a time that is convenient for both you and the tradesperson.
Why do I need to complete hipages' question and answer form?
What is your returns policy for exhaust and heat lamp installations?
I have lost my installation card, who should I contact?
If you have lost your installation card, contact your local Bunnings to arrange a new card.
One of the products installed was damaged/faulty, what are my options?
I have changed my mind, can I return the installation card to Bunnings?
If you have not activated the voucher then it can be returned to Bunnings for a full refund.
How do I return a product that is currently installed?
Exchanges on non-faulty goods are only available prior to installation.
The item installed was the wrong size/colour, will you exchange it?
Exchanges on non-faulty goods are only available prior to installation. For faulty goods, please refer to our returns policy.
One of the products installed has an installation issue, can I get a refund?
How do I pay for this installation service?
Simply pick up an exhaust or heat lamp and installation card in-store and pay at the register or the Special Orders desk.
replacement of one exhaust or heat lamp and site clean-up.
An exhaust or heat lamp installation will take approximately 45 minutes to 1 hour.
Will you take away my exhaust or heat lamp?
Disposal of the old exhaust or heat lamp is not included in this offer.
What if my tradesperson requires additional parts?
Standard installation is included in the price, any charges related to non-standard installation are to be paid to the tradesperson directly.
What if I am unhappy with the installation?
Who will install my bathroom heat lamp?
A licensed and professional tradesperson.
Who do I speak to if I have any installation problems?
How do I return a product that has been installed?
Exchanges on non-faulty goods are available prior to installation. For faulty goods, please refer to our returns policy.
Exchanges are only available prior to installation.
Bunnings installation services are provided by hipages in partnership with Bunnings. Please ensure you have read and understood the terms and conditions.
The service is available to residential customers only.
Price is based on one exhaust or heat lamp installation per voucher.
Standard installation is included in the price, any charges related to non-standard installation are to be paid to the tradesperson directly. Ceiling patching or painting is not included in the standard installation.
All installations are conducted on a like-for-like basis. This means that the incoming product can be installed in the same position and with the same connections/configurations as the outgoing product.
This offer does not provide an initial install for a new exhaust or heat lamp, an existing exhaust or heat lamp must be present and in place of where the new unit is to be installed.
If the new exhaust or heat lamp requires ducting/ventilation it must be replacing a ducted unit. Exhausts or heat lamps that use an inline fan with the ducting have been excluded from the offer. All ducting/ventilation must be present and compliant.
Ceiling height cannot exceed 2.85 metres and must be free from asbestos. Exhaust or heat lamps are not able to be installed in a concrete ceiling.
Current wiring to the unit must be present and compliant, rewiring or new wiring is not included in the fixed price offer.
If any conditions are not met or additional work is required to make the install compliant, then additional charges may apply.


text:
Building the DMP of tomorrow starts with these three tenets of identity
Currently, marketers don't have a single source of truth about their consumers. Tomorrow, there must be a single place to build consumer profiles with rich attribute data, and provisioned to the systems of engagement where that consumer spends their time.
By Chris O'Hara	 February 1st 2018 13:24
At a recent industry event, we heard a lot about the upcoming year in marketing, and how data and identity will play a key role in driving marketing success.
As a means to master identity, some companies have heralded the idea of the customer data platform (CDP), but the category is still largely undefined. For example, many Salesforce customers believe that they already have a CDP. The reason? They have several different ways of segmenting known and unknown audiences between a data management platform (DMP) and CRM platform.
In an article I wrote here last year, I introduced a simple "layer cake" marchitecture, describing the three core competencies for effective modern marketing. In such a fast moving and evolving industry, I have since refined it to the core pillars of identity, orchestration and intelligence:
With this new marchitecture, brands have the ability to know consumers, engage with them through each touchpoint and use artificial intelligence to personalize each experience.
Mastering each layer of complexity is difficult, requiring an investment in time, technology and people. Lets focus on perhaps the most important – the data management layer where the new CDP category is trying to take hold.
The next wave of data management
By now, it's safe to say marketers have mastered managing known data. A few years ago, when I was working for a software company that also managed postal mailing lists, I was astonished at the rich and granular data attached to mailing lists. There is a reason direct mail companies can justify $300 CPMs – it works, because direct marketers truly know their customers.
After joining Salesforce, I was similarly awed by the power to carefully segment CRM data, and provision journeys for known customers spanning email, mobile, Google and Facebook, customer service interactions and even community websites.
How can we get to this level of precision in the world of unknown (anonymous) consumer data?
As marketing technology and advertising technology converge, so must the identity infrastructure that underlies both. Put more simply, tomorrow's systems need a single, federated ID that is trust-based. Companies must have a single source of truth for each person, the ability to attach various keys and IDs to that unified identity, as well as have a reliable and verifiable way to opt people out of targeting.
Let's take a look at what that might look like:
This oversimplification looks at the various identity keys used for each system and the channels they operate in. Today, the CRM is the system of record for engaging consumers directly in channels like direct mail, email campaigns and service call centers. The DMP, on the other hand, is the system of record for more passive, anonymous engagement in channels like display, video and mobile.
When consumers make themselves known, they "pull" engagement from their favorite brands by requesting more information and opting into messaging. At the top of the funnel, we "push" engagements to them via display ads and social channels.
As a marketer, if you have the right technologies in place, you can seamlessly connect the two worlds of data for more precise consumer engagement. The good news is that, martech and adtech have already converged. Recent research from Salesforce shows that 94% of marketers use CRM data to better engage with consumers through digital advertising, and over 91% either already own or plan to adopt DMP over the next year.
So, if mastering consumer identity is the most important element in building tomorrow's data platform then what, exactly, are the capabilities that need to be addressed? There are three:
1. A single data segmentation engine
Currently, marketers don't have a single source of truth about their consumers.
Here's why: Brands build direct mail lists and email lists in their CRM. Separately, they build digital lists of consumers in a DMP tool. Then, they have lists of social handles for followers in various platforms like Facebook and Twitter. Consumer behaviors like browsing and buying that happen on the ecommerce platforms are often not integrated into a master data record. And distributed marketing presents a challenge because a big mobile company or auto manufacturer may have thousands of franchised locations with their own, individual databases.
Segmentation is all over the place. Tomorrow, there must be a single place to build consumer profiles with rich attribute data, and provisioned to the systems of engagement where that consumer spends their time.
2. Data pipelining and governance capabilities
This identity layer must also have the ability to provision data, based on privacy and usage restrictions, to systems of engagement.
For example, when a consumer buys shoes, they should be suppressed from promotions for that product across all channels. When a consumer logs a complaint on a social channel, a ticket needs to be opened in the call center's system for better customer service. When a person opts out and chooses to be "forgotten," the system needs to have the ability to delete not only email addresses, but hundreds of cookies, platform IDs and other addressable IDs in order to meet compliance standards with increasingly restrictive privacy laws and, more importantly, giving consumers control over their own data.
Finally, marketers need the ability to ingest valuable DMP data back into their own data environments to enrich user profiles, perform user scoring, as well as build propensity models and lifetime value scores. This requires granular data storage, fast processing speeds and smart pipelines to provision that data.
3. Leaping from DMPs to holistic data management
Ad technology folks are guilty of thinking of cross-device identity (CDIM) as the definition of identity management. Both deterministic and predictive cross-device approaches are more important than ever, but in a world where martech and adtech are operating on the same budgets and platform, today's practitioner must think more broadly.
Marketers can no longer depend solely on another party's match table to bridge the divide between CRM and DMP data. A more durable, and privacy-led connector between known and unknown ID types is required. Moreover, when they can, marketers need the ability to enrich email lists with anonymous DMP attributes to drive more performance in known channels—now only possible when a single party manages the relationship.
These three tenets of identity are the starting point for building the data platform of the future. The interest and excitement around CDPs is well placed, and a positive sign that we are evolving our understanding of identity as the driving force behind the changes in marketing.
Need some CRM training? Try Econsultancy's face-to-face courses.
Article CRM Data and Analytics UK US
Article Data and Analytics
The three trends driving marketing analytics in 2018
In this era of data-driven everything, the need for high-quality marketing analytics has never been greater.
Yet for many companies, marketing analytics still consists of a weekly report and perhaps a dashboard or two.
February 2nd 2018 15:16
Article Innovation and Trends
How AI is transforming healthcare
It's fair to say that artificial intelligence has become a part of our daily lives. The average person doesn't think twice about letting an algorithm provide music recommendations or directions on how to get from A to B.
February 12th 2018 14:27
There are 4 comments	at the moment, we would love to hear your opinion too.
Matt Lovell 2 February 2018
The other point I would flag within your data pipelining section is that at the moment despite a wide range of companies now implementing DMPs, there isn't the real time connectivity between systems to ensure that when something about a user changes, that data can be passed to all other parts in real time to ensure the user's experience is aligned. I've no doubt that this will change in the coming months but it feels like it's an aspect that for now is very much lagging behind.
Chris O'Hara 2 February 2018
Thanks for the comment, Matt. You are 100% right. It's most certainly on the way, but challenging due to the fact that–even if your DMP can process and "pitch" the data in near real time, the systems on the other side have to "catch" it, and many are built on legacy technology that are still being updated.
James Gaitskell 2 February 2018
Matt, I think you've got it spot on. Real-time bi-directional connectivity hydrating data into every endpoint is the only way to achieve situational context – and context is king. You need a CDP that enables ALL data to be eligible and free to participate.
On the point of marketers have mastered known data, I'm not sure this is the case. Once upon a time, this was true, but the web era has perhaps created a reliance on ad-tech which has left first party data by the wayside in many ways.
Mobile and GDPR have and will fundamentally change that. Mobile creates vastly more complex and rich data points that feed situational context, and GDPR will force marketers to sharpen the saw and create better value-exchanges to unlock consent for this data.
I'm excited for the new era of better customer experiences, but it will require businesses to invest in the very best marketing technology for the connected era. The CDP space is set to get very exciting – it also opens up great opportunities to build a best of breed stack of the most modern marketing tech out there, with east and flexibility. The marketing ecosystem looks very different now, as consumers gravitate towards mobile and resulting connected experiences that are unfolding.
jordan gilman 2 February 2018
Great article, we have felt strongly about this for almost 5 years. We've been building a platform called PeopleVine which provides marketers with the tools to engage across multiple channels (not just social and email, but live interactions and more). We are still young, but our platform is exactly what you're looking speaking about.
Would love to chat, reach out at PeopleVine.com.


text:
Sam Adams
Calling someone a survivor is like praising him or her for not playing in traffic; survival is, after all, a trait as common in microorganisms as in pop stars. But Marianne Faithfull has walked to the brink more times than most, confronting death and ruin, sometimes of her own making, and finding her way back. Compare the angelic soprano of "As Tears Go By," the melancholy, slightly saccharine single that introduced her to the world in 1964, with the cracked alto on this year's Horses And High Heels, and you can hear the way age and hard living have seeped into the fissures in her voice.
Faithfull's is one of the more extraordinary reinventions in the history of pop music. She was a budding pop starlet enjoying the visibility of dating Mick Jagger at the height of the British Invasion when a notorious drug bust tarnished her public image and sent her tumbling into years of addiction. Then, in 1979, she reappeared with Broken English, a harrowing chronicle of obsession and recrimination laced with angry synthesizers and stinging guitars. In the decades since, she's established herself as a prime interpreter of the songs of Bertolt Brecht and Kurt Weill, and made inroads with a new generation by collaborating with the likes of Jarvis Cocker and PJ Harvey. On Horses And High Heels, produced by Hal Willner, Faithfull tries her hand at a typically eclectic assortment of cover songs, from "Back In Baby's Arms" to a sorrowful version of Knoxville songwriter and playwright RB Morris' "That's How Every Empire Falls"; but the highlights are the songs she wrote herself, which delve into her personal history with unprecedented clarity. Shortly after the album's release, Faithfull spoke with The A.V. Club about her love of vinyl, the end of The News Of The World, and why her life is like an episode of Seinfeld.
The A.V. Club: There are some surprising cover choices on Horses And High Heels, like The Shangri-Las' "Past Present And Future," but the songs you wrote yourself are startling in a different way. There's a real lyrical transparency, almost a plainspoken quality, to some of them.
Marianne Faithfull: I know, I'm very direct now. I've simplified much more in my writing. I say what I've got to say, not in metaphor. It's all things that are literally happening. Even "you listen to the rain falling," it's something that's happening. It's not an image.
AVC: What drove you toward writing more simply?
MF: It's this really interesting thing to follow the truth, to make sure that it actually fits in with what really happened. I'm not sure I'll do it on my next one. I might go more back into metaphor and atmosphere. This is the first time I've worked so consciously on making the songs reflect what really happened, and I think it was really effective.
AVC: One in particular "Why Did We Have To Part," which is about the end of a 15-year relationship with your manager, François Ravard.
MF: That's so blunt. It's almost shocking for me that it should be so blunt. But what else can I do? I have to tell the story as it actually happened.
AVC: Is it cathartic for you? Does it help you sort through things?
MF: Unfortunately not. I mean, in the end it is of course, but when it was actually happening, which wasn't very long ago, three years, I couldn't write. I got blocked. That's why I put out [the covers album] Easy Come, Easy Go, to get me through that. Then it came back, and then I was able to write, "Why Did We Have To Part."
AVC: That and the title track, although that's farther back, there's a tangible sense of time passing.
MF: It's not that long ago, it's about 10 years ago when I was living in Ireland.
AVC: So that's a true story as well?
MF: Yeah. It took time, because for the song to be really interesting it had to be two places. It wouldn't have been interesting if it was just in Dublin. What's interesting about that song isn't really stuff I'm seeing, it's what I'm hearing. Which is how I really live. It's sound that attracts me. And the horses and the hot girls in Paris with the high heels on the cobblestones sounded the same. The echo, that was very important, from the houses on each side. It was a good sound.
AVC: When you said that sound attracts you, has that always been the case, and what does that mean?
MF: Words to conversation, talk, yes. Yes.
AVC: Is that why you are drawn to music and musicians?
MF: Yes, but I had no idea at the time. I thought I wanted to go to drama school or university, and that would have been a completely different life. But what got me was the sound, and hearing it. Hearing everything so loud, I loved that back in the studio. I loved that from the very beginning.
AVC: People often don't realize that loud, amplified music was very much a novelty in the '60s. Part of the reason that no one could hear the Beatles over the crowd at Shea Stadium was that the P.A. system just wasn't that powerful.
MF: The equipment you've got really dictates what you're going to do. When I started touring, there were no monitors, so I had to take the sound from the hall, and of course it was on a delay, so I would sing, and then I would hear it back, but later. It was very weird.
AVC: The promotional video for Horses And High Heels devotes a significant amount of time to talking about using analog recording equipment. That's something that's important to you?
MF: It's a huge deal. It changes the sound completely. I don't like the compression on compact discs. It's lacking in air, and it's lacking in majesty. The vinyl is just about to come out here, and I seriously recommend it, apart from the fact that there are two songs on the vinyl that aren't on the record, and they're lovely. Hal [Willner] and I had a big argument about that. He wanted to put "Past Present And Future" [as a vinyl bonus track] and I wasn't so sure. It seems that people really like it in America, but they don't like it Europe. They don't get it.
AVC: That's certainly one of the more…
MF: Outré. It's a joke really. Not completely serious. Really.
AVC: Are the vinyl songs covers as well?
MF: Yeah, really beautiful ones. "I Don't Want To Know," which is a wonderful song, and another really great song called "Fragile Weapon."
AVC: Along with "Past Present And Future," "Goin' Back," originally written by Carole King and made famous by Dusty Springfield, is probably the best-known cover on the album,
MF: They're playing with time.
AVC: There's a real, concrete sense of time and place on the album, especially on "Horses And High Heels" and "Prussian Blue."
MF: "Prussian Blue" is about Paris, and nothing much happens in it. I wanted that very much, because I wanted to make it quite clear that I'm not actually a tragedy queen living a high-drama life. I live a very nice life. I have a wonderful time. But it's not lived drawing on a full level. I'm relaxed, cool, and enjoying it. It's no different to Curb Your Enthusiasm or Seinfeld, actually. Nothing really ever happens, but life goes on, and I like that. If I do another record, I might use more atmospheric stuff, but this was an experiment, and I think it worked.
AVC: The record has a very earthy sound. You recorded in New Orleans, with musicians like The Meters' George Porter, Jr.
MF: He's incredible. And Doug [Pettibone] is very good, and John Porter was great. And Lou [Reed], and Mac [Rebennack]—and Wayne [Kramer], of course. I took Wayne on tour with me through Europe. I started touring with him in March, so we'd been working with Wayne Kramer, but I couldn't afford it here. In Canada, he couldn't get in anyway because he has a history. [Laughs.] I couldn't afford to do that, and he didn't really want to yet. But he will, I'm sure.
AVC: Speaking of your more atmospheric, Broken English was a huge break from what you'd done before.
MF: It was a wonderful record.
AVC: It's hard to imagine the impact that sound would have had at the time.
MF: Straight from the streets. Straight from being a drug addict. It was pretty radical. And it was true. That's always interesting. It couldn't go on like that. I didn't want to be angry, twisted and bitter all my life, so I had to change. And I did. Maybe it wasn't quite as exciting and knife-edge.
AVC: What drew you to writing about the Red Army Faction's Ulrike Meinhof on the title track?
MF: I read a book about it, so that interested me. Before Broken English, even, I was touring with that band, and we'd gone to look at the [Berlin] Wall, me and Barry [Reynolds], and it made a deep impression on me. I think I understood it, actually, the repressed Protestant thing, and very cold, and very lonely. So I read this book about the Baader-Meinhof gang, and then I was watching something on the television. I don't remember really what it was about, but it had subtitles, and they came on and they said, "Broken English, spoken English." I immediately wrote that down, and then I wrote the song.
AVC: There's a degree of empathy in the song, but you're also addressing her: "What are you fighting for?"
MF: Yeah, it was like that in the beginning. Of course now, "Broken English," the whole thing has widened, and it's different. I even say, "What are we fighting for?" now. I take it more personally.
AVC: The title could almost have referred to you at the time: broken, English.
MF: What I'm really doing, I can tell you exactly—what I recognized is that there are a certain kind of neurosis that could express itself in terrorism, and anger out. One thing is sure, to be a drug addict, the anger is all going in. You're hurting yourself. But with a terrorist like Ulrike Meinhof, she's hurting other people, and that interested me. I could feel "There but for the grace of God…." I was very glad I wasn't a terrorist. I wasn't that happy to be a drug addict, but anyway, I got over it.
AVC: You've said you're not as angry now as you were then, although you can slip back into that mindset for the space of "How'd Ya Do It?"
MF: It's very important to me, and I'm not. I'm free. It's not that I put the '60s down, and I don't. I'm very grateful to the Stones for the songs that we worked on together, and to Mick Jagger, I'm very grateful, but it's not really my story. It's a little part of it. It was four years out of my life. But I did come up very angry, and that's helped me a lot, because what I realized later is that anger is not actually a bad thing. It's just a kind of energy, really. I can pull it out even now when I'm singing "Broken English" onstage, and I can leave it alone. I don't carry it with me. It's not in me.
AVC: Part of your explanation for the gaps in your songwriting career is that in order to write songs, you have to go deep inside yourself, and sometimes that's a dangerous thing.
MF: For me it is. I don't want to stir up any embers of all that.
AVC: When you first started recording, a woman's job was basically to look pretty and sing nicely. It wasn't supposed to be your story.
MF: Yeah, I was awfully beautiful—that was the trouble. Until you learn to protect yourself, that can be a very dangerous and unhappy-making thing, because I also didn't really know. There's nothing as beautiful as a girl who is beautiful but doesn't know she's beautiful, utterly charming. I was terribly innocent. I was just out of college. It was only two years after I had left school that I ran off with Mick. I didn't know anything about men, certainly nothing about drugs, and nothing about sex, none of that. I really didn't know.
AVC: You said that after 1967, where you were caught in a drug bust at Keith Richards' house and the tabloids got a hold of the story…
MF: The perception of me changed completely, but it was wrong.
AVC: You said there was a point at which you thought, "If people think this is what I am, this crazy, high-living drug addict, I might as well play the part."
MF: I think I did say that to myself. Fuck 'em. I think I actually said, I wish I hadn't, but I said that, "Might as well be hung as a sheep as a lamb." When I said that I knew nothing. It was my first acid trip, and that was the only drug I had ever taken.
AVC: Was The News Of The World one of those papers?
MF: Yeah. It was News Of The World, it was all News Of The World, and a few other papers. I must say, when I read my New York Times this morning, and I read that News Of The World is going out of business, I got a bit of quiet satisfaction. Like, "Thank God, finally," and for that reason. They were absolutely unscrupulous, tapping phones, and they did that with us.
AVC: You said in your first autobiography, Faithfull, that you did heroin before going onstage as Ophelia in Hamlet, to soothe stage fright.
MF: Yeah, I think… No, I think it was before the mad scene, that's what I was using it for. I didn't take it before the play, the whole play, just before the mad scene. It was very effective, but it was very dangerous.
AVC: How did that work with the film of Hamlet?
MF: I don't think I took it then. I was clean then. I think it was something very concentrated, and I decided not to. I wasn't hooked yet.
AVC: Was there something about being onstage opposite Shakespearean actors like Nicol Williamson, or the role in particular?
MF: It was the role. I ended up like a suicide after that, because I hadn't been trained, and I was acting, really, like a child would. I was believing that I was Ophelia, and actually got really into it, and that's really directly connected to what happened in Australia. [In 1969, Faithfull overdosed on barbiturates and was in a coma for six weeks. —ed.] She haunted me. I don't really want to go on about this much—the fucking '60s, it's like a noose hanging around my neck. All this stuff isn't relevant really now at all, and hasn't been for years, and it's that that lends the tragic element to my life. I mean, I got off drugs and stopped being so tragic.
AVC: What's fascinating musically is to hear you come back to "As Tears Go By" now.
MF: Or like "Strange Weather," when I rerecorded that.
AVC: Was that a matter of laying claim to it yourself?
MF: I think so, yeah. Owning it. And it worked. But now when I'm onstage I do the first version. I've changed. I don't want to do the sad version.
AVC: The original "As Tears Go By" has this kind of airy, fluttering quality.
MF: It's bouncy, it's very, very poppy. I think what I also wanted to show was the depth of the song. It's a really good song, and it's got real staying power, and I can still sing it. And it works, I still sing it, and people love it.
AVC: "Sister Morphine" was another one that you had a second go at.
MF: Yeah, obviously, because I was really ill when I did that. I was on drugs, so I did want to rerecord it not on drugs, but it wasn't quite as interesting. It's really good now, of course, when I do it live. It's excellent. It's spellbinding. It's partly because I'm so good at what I do. If I sing this song about Sister Morphine, people immediately think I am Sister Morphine, which is not true. Not at all, but that's how people started to think. I've battled against that for years. I think it's over now. I've done it.
AVC: How do Brecht and Weill come into the picture?
MF: They come into it a lot because I started studying alienation, Brechtian, and I'm very happy that people can pick that up. It's been great for me, because it stops me being hurt by the songs.
AVC: It's the opposite approach of how you played Ophelia, when you felt you had to be the character in real life.
MF: But I did feel like that. I had read Stanislavski, and I did play Ophelia as if I was Ophelia, and I actually believed I was Ophelia.
AVC: Brecht doesn't want actors to lose themselves in their characters, or the audience to forget they're watching a play.
MF: No, and after I studied alienation I never did again. It can be the character in a song, it can be the character in a play, it can be anything.
AVC: Is that still the case? When there are autobiographical songs, like on Horses And High Heels, does that become a character eventually?
MF: That's me, and I am completely recognizable, and I am myself, and I am not in a trauma. I'm like I was before I took drugs. I'm not consciously practicing alienation. I'm sure that I have a little bit of it, but I'm not consciously doing it. I don't need to. But there is emotion. It has that slight twist.
AVC: A lot of performers, at least the ones who do grow old, learn how much of themselves they can put into their work without endangering themselves.
MF: You don't have to be the character. I can really come at it as I am. A working artist, that's what I am.
AVC: That can be a profound thing on its own.
MF: That can be, yeah. "Goin' Back" was recorded in one take. That was one of my best tricks I ever did. In that take, I got this flood of emotion, because I do feel those things, I really do. "I'd rather see the world the way it used to be." I would.
AVC: It's funny to think of "Goin' Back" being written by someone in her 20s.
MF: Carole, yeah, very young. Dusty, too. They were both young. It was a perfect moment for that because of the drugs. Somebody like Carole King is such a genius. She was seeing into life much more than anyone else at the time.
AVC: When you sing "Goin' Back" now, more of its melancholy wisdom comes to the surface. Some versions, it's easy not to absorb the fullness of what the song is about.
MF: Because they're not concentrating on the lyrics. Several people who have recorded have left out the wonderful line — [Laughs.] '60s, really '60s —"Let everyone debate the true reality." People don't go 'round debating the true reality now, but we did, deeply and very, very intensely.


WTF?! In December, Samsung announced a partnership with Supreme (or should we say "Supreme"). Once it was found out that the company was working with Supreme Italia, a knockoff of the actual NYC-based company, Samsung was the subject of ridicule and embarrassment. In a frenzy to save face, Samsung tried to parlay the ill-fated partnership as intentional, but today caved to pressure to call it off.
Samsung has mercifully ended its collaboration with a fake version of fashion brand Supreme, quietly issuing a statement via Chinese social media platform, Weibo.
In a rather bizarre string of events, the company announced its collaboration with Supreme in December 2018 during an event in China. Samsung introduced two people posing as Supreme CEOs, who walked on stage to announce the opening of a flagship store in Beijing.
As it turns out, Samsung had been duped into working with "Supreme Italia," an Italian knockoff brand with no relation to the NYC-based Supreme. Supreme Italia was operating legally due to the failure of the real Supreme to defend its trademark earlier in the year. This forced NYC Supreme to issue a statement saying they were not working with Samsung, and were not opening a store in Beijing. Samsung then tried to save face by acting as though they were intending on working with the Italian knockoff all along. Got all that?
Samsung had originally pursued a partnership with the counterfeit Supreme Italia due to their license to sell its wares in China - a market in which Samsung is rapidly expanding. With the deal dead, Supreme fanatics everywhere will never know what products this collaboration was meant to bring to market.


DUE TO MASSIVE DEMAND FOR OUR DELICIOUS SAMPLE PODS WE HAVE HAD TO CLOSE OUR SAMPLE PROGAM EARLY!
We apologize for any inconvenience and hope we didn't let you down!
For today only, we're offering EVERYONE our friends and family pricing on ALL packages of Subscriptions AND Single Orders.
My moms gonna kill me!
Simply use the code FRIENDSANDFAMILY15 at checkout and you will receive 15% off your entire first Subscription or Single Order!
15% discount for your first order!
Enter your email for your discount code that can be applied toward your first month's subscription!
Century Coffee Club is not affiliated with, endorsed, or sponsored by Nespresso or any of its affiliates.


Jay Som and Justus Proffit Share New Single, "Invisible Friends"
Jay Som and Justus Proffit have shared "Invisible Friends," a new song from their forthcoming collaborative EP Nothing's Changed, out Sept. 28 on Polyvinyl Records.
The recording project came together after Duterte moved to L.A. following her 2017 album Everybody Works. There she found a kindred spirit in L.A.-based songwriter Justus Proffit. The two immediately hit it off, and their impromptu jam sessions soon snowballed into the forthcoming EP. The pair wrote and recorded one song per day, with Duterte tracking and mixing, Proffit handling lyrics and drums, and the both of them sharing vocal and guitar duties. The end result is Nothing's Changed. "It felt more like a school project than a recording project," Proffit said. "I think we both challenged each other with each song, forcing ourselves to either stick to an idea or move on, and accept mistakes," Duterte added.
The pair will be touring together for the remainder of the year—keep scrolling for those dates.
Listen to "Invisible Friends" below.


text:
Ethelreda, Etheldreda or Ethreda was a daughter of Gospatric, Earl of Northumbria remembered in 13th century Cumberland as the mother of William fitz Duncan.

She married Duncan II of Scotland, King of Alba. Ethelreda was Queen Consort of Alba for about six months in 1094, until Duncan's death on 12 November 1094.

After Duncan was killed by Mormaer Máel Petair of Mearns, it is probable that Ethelreda fled with at least one child, William fitz Duncan, to the safety of Allerdale in Cumberland, where her brother Waltheof was lord.

The Chronicon Cumbriæ reports that Waltheof granted Broughton, Ribton and Little Broughton jointly to his sister Ethelreda and Waltheof, son of Gillemin, who would be another husband. More of Waltheof of Allerdale's lands would eventually be inherited by Ethelreda's son William fitz Duncan.

References

 William M. Aird, "Gospatric, earl of Northumbria (d. 1073x5)", Oxford Dictionary of National Biography, Oxford University Press, 2004 , retrieved 13 Feb 2009
 A. A. M. Duncan, "Duncan II (b. before 1072, d. 1094)", Oxford Dictionary of National Biography, Oxford University Press, 2004 , retrieved 13 Feb 2009
 James Wilson, ed., The Register of the Priory of St. Bees, Surtees Society, 1915, pp. 491–5

Scottish royal consorts
11th-century Scottish people
11th-century Scottish women
House of Dunkeld

redpajama_set_name: RedPajamaWikipedia