ECCC-Report TR15-115https://eccc.weizmann.ac.il/report/2015/115Comments and Revisions published for TR15-115en-usTue, 21 Jul 2015 07:10:23 +0300
Paper TR15-115
| A Guide to Learning Arithmetic Circuits |
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2015/115An \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}Tue, 21 Jul 2015 07:10:23 +0300https://eccc.weizmann.ac.il/report/2015/115