TR15-202 Authors: Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

Publication: 11th December 2015 11:43

Downloads: 1440

Keywords:

Polynomial Identity Testing (PIT) algorithms have focused on

polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted

formulas. Read-once polynomials (ROPs) are computed by read-once

formulas (ROFs) and are the simplest of read-restricted polynomials.

Building structures above these, we show the following:

\begin{enumerate}

\item A deterministic polynomial-time non-black-box PIT algorithm for

$\sum^{(2)}\cdot \prod \cdot {ROF}$.

\item Weak hardness of representation theorems for sums of powers of constant-free ROPs and for

ROPs of the form $\sum \cdot \prod \cdot \sum$.

\item A partial characterization of multilinear monotone constant-free ROPs.

\end{enumerate}