ECCC-Report TR15-202https://eccc.weizmann.ac.il/report/2015/202Comments and Revisions published for TR15-202en-usFri, 11 Dec 2015 11:43:01 +0200
Paper TR15-202
| Building above read-once polynomials: identity testing and hardness of representation |
Meena Mahajan,
Raghavendra Rao B V,
Karteek Sreenivasaiah
https://eccc.weizmann.ac.il/report/2015/202Polynomial 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}Fri, 11 Dec 2015 11:43:01 +0200https://eccc.weizmann.ac.il/report/2015/202