Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-115 | 20th July 2015 20:45

A Guide to Learning Arithmetic Circuits

RSS-Feed




TR15-115
Authors: Ilya Volkovich
Publication: 21st July 2015 07:10
Downloads: 942
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