Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

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 ...
more >>>