__
TR15-115 | 20th July 2015 20:45
__

#### A Guide to Learning Arithmetic Circuits

**Abstract:**
An \emph{arithmetic circuit} is a directed acyclic graph in which the operations are $\{+,\times\}$.

In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems.

In particular, we show that:

\begin{enumerate}

\item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds.

\item General circuits and formulas can be learned efficiently with membership and equivalence queries iff

they can be learned efficiently with membership queries only.

\item Low-query, learning algorithms for certain classes of circuits imply explicit rigid matrices.

\item Learning algorithms for multilinear depth-3 and depth-4 circuits must compute square roots.

\end{enumerate}