A Guide to Learning Arithmetic Circuits
Abstract
An \empharithmetic 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: \beginitemize \it{em} Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds. \it{em} General circuits and formulas can be learned efficiently with membership and equivalence queries iff they can be learned efficiently with membership queries only. \it{em} Low-query learning algorithms for certain classes of circuits imply explicit rigid matrices. \it{em} Learning algorithms for multilinear depth-3 and depth-4 circuits must compute square roots. \enditemize
Cite
Text
Volkovich. "A Guide to Learning Arithmetic Circuits." Annual Conference on Computational Learning Theory, 2016.Markdown
[Volkovich. "A Guide to Learning Arithmetic Circuits." Annual Conference on Computational Learning Theory, 2016.](https://mlanthology.org/colt/2016/volkovich2016colt-guide/)BibTeX
@inproceedings{volkovich2016colt-guide,
title = {{A Guide to Learning Arithmetic Circuits}},
author = {Volkovich, Ilya},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2016},
pages = {1540-1561},
url = {https://mlanthology.org/colt/2016/volkovich2016colt-guide/}
}