Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-115 | 20th July 2015 20:45

#### A Guide to Learning Arithmetic Circuits

TR15-115
Authors: Ilya Volkovich
Publication: 21st July 2015 07:10
Keywords:

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}

ISSN 1433-8092 | Imprint