Learning Restricted Models of Arithmetic Circuits
by Adam Klivans and Amir Shpilka
Theory of Computing, Volume 2(10), pp. 185-206, 2006
Bibliography with links to cited articles
| [1] |
D. Angluin: Queries and concept learning.
Machine Learning, 2:319-342, 1988.
[ML:l147k68714mhg8m5]. |
| [2] |
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy: Proof
verification and the hardness of approximation problems.
Journal of the ACM, 45(3):501-555, 1998.
[JACM:278298.278306]. |
| [3] |
J. Aspnes, R. Beigel, M. Furst, and S. Rudich: The expressive power of
voting polynomials.
In Proc. 23rd STOC, pp. 402-409. ACM Press, 1991.
[STOC:103418.103461]. |
| [4] |
A. Beimel, F. Bergadano, N. H. Bshouty, E. Kushilevitz, and
S. Varricchio: Learning functions represented as multiplicity automata.
Journal of the ACM, 47(3):506-530, 2000.
[JACM:337244.337257]. |
| [5] |
F. Bergadano, N. H. Bshouty, C. Tamon, and S. Varricchio: On learning
branching programs and small depth circuits.
In Proc. of the 3rd European Conf. on Computational Learning
Theory (EuroCOLT'97), volume 1208 of LNCS, pp. 150-161, 1997.
[lncs:73001q2141150g25]. |
| [6] |
F. Bergadano, N. H. Bshouty, and S. Varricchio: Learning multivariate
polynomials from substitution and equivalence queries.
Electronic Colloquium on Computational Complexity, 3(8), 1996.
[ECCC:TR96-008]. |
| [7] |
F. Bergadano and S. Varricchio: Learning behaviors of automata from
multiplicity and equivalence queries.
SIAM Journal on Computing, 25(6):1268-1280, 1996.
[SICOMP:10.1137/S009753979326091X]. |
| [8] |
D. Bshouty and N. H. Bshouty: On interpolating arithmetic read-once
formulas with exponentiation.
Journal of Computer and System Sciences, 56(1):112-124, 1998.
[JCSS:10.1006/jcss.1997.1550]. |
| [9] |
N. H. Bshouty, T. R. Hancock, and L. Hellerstein: Learning arithmetic
read-once formulas.
SIAM Journal on Computing, 24(4):706-735, 1995.
[SICOMP:10.1137/S009753979223664X]. |
| [10] |
N. H. Bshouty, T. R. Hancock, and L. Hellerstein: Learning boolean
read-once formulas over generalized bases.
Journal of Computer and System Sciences, 50(3):521-542, 1995.
[JCSS:10.1006/jcss.1995.1042]. |
| [11] |
N. H. Bshouty and Y. Mansour: Simple learning algorithms for decision
trees and multivariate polynomials.
SIAM Journal on Computing, 31(6):1909-1925, 2002.
[SICOMP:10.1137/S009753979732058X]. |
| [12] |
N. H. Bshouty, C. Tamon, and D. K. Wilson: On learning width two
branchinng programs.
Information Processing Letters, 65(4):217-222, 1998.
[IPL:10.1016/S0020-0190(97)00204-4]. |
| [13] |
J. W. Carlyle and A. Paz: Realizations by stochastic finite automata.
Journal of Computer and System Sciences, 5(1):26-40, 1971. |
| [14] |
M. Fliess: Matrices de Hankel.
Journal de Mathématiques Pures et Appliquées,
53:197-224, 1974. |
| [15] |
D. Grigoriev and M. Karpinski: An exponential lower bound for depth 3
arithmetic circuits.
In Proc. 30th STOC, pp. 577-582. ACM Press, 1998.
[STOC:276698.276872]. |
| [16] |
D. Grigoriev, M. Karpinski, and M. F. Singer: Computational complexity of
sparse rational interpolation.
SIAM Journal on Computing, 23(1):1-11, 1994.
[SICOMP:10.1137/S0097539791194069]. |
| [17] |
D. Grigoriev and A. A. Razborov: Exponential complexity lower bounds for
depth 3 arithmetic circuits in algebras of functions over finite fields.
In Proc. 39th FOCS, pp. 269-278. IEEE Computer Society Press,
1998.
[FOCS:10.1109/SFCS.1998.743456]. |
| [18] |
T. R. Hancock and L. Hellerstein: Learning read-once formulas over fields
and extended bases.
In Proc. of the 4th Ann. Conf. on Computational Learning Theory
(COLT '91), pp. 326-336. Morgan Kaufmann, 1991.
[ACM:114836.114867]. |
| [19] |
J. Håstad: Almost optimal lower bounds for small depth circuits.
In Proc. 18th STOC, pp. 6-20. ACM Press, 1986.
[STOC:12130.12132]. |
| [20] |
M. A. Huang and A. J. Rao: Interpolation of sparse multivariate
polynomials over large finite fields with applications.
Journal of Algorithms, 33(2):204-228, 1999.
[JAlg:10.1006/jagm.1999.1045]. |
| [21] |
J. C. Jackson, A. R. Klivans, and R. A. Servedio: Learnability beyond
AC0.
In Proc. 34th STOC, pp. 776-784. ACM Press, 2002.
[STOC:509907.510018]. |
| [22] |
A. Klivans and A. Shpilka: Learning arithmetic circuits via partial
derivatives.
In Proc. of the 16th Ann. Conf. on Learning Theory (COLT '03),
pp. 463-476, 2003.
[COLT:48b02anqvmv32a6j]. |
| [23] |
A. R. Klivans and D. Spielman: Randomness efficient identity testing of
multivariate polynomials.
In Proc. 33rd STOC, pp. 216-223. ACM Press, 2001.
[STOC:380752.380801]. |
| [24] |
N. Linial, Y. Mansour, and N. Nisan: Constant depth circuits, Fourier
transform and learnability.
Journal of the ACM, 40(3):607-620, 1993.
[JACM:174130.174138]. |
| [25] |
N. Nisan: Lower bounds for non-commutative computation.
In Proc. 23rd STOC, pp. 410-418, 1991.
[STOC:103418.103462]. |
| [26] |
N. Nisan and A. Wigderson: Lower bounds on arithmetic circuits via
partial derivatives.
Computational Complexity, 6(3):217-234, 1997.
[CC:v34728p847187762]. |
| [27] |
H. Ohnishi, H. Seki, and T. Kasami: A polynomial time learning algorithm
for recognizable series.
IEICE Transactions on Information and Systems,
E77-D(10):1077-1085, 1994. |
| [28] |
R. Raz: Multi-linear formulas for permanent and determinant are of
super-polynomial size.
In Proc. 36th STOC, pp. 633-641. ACM Press, 2004.
[STOC:1007352.1007353]. |
| [29] |
R. Raz: Separation of multilinear circuit and formula size.
Theory of Computing, 2(6):121-135, 2006.
Preliminary version appeared in FOCS'04, pp. 344-351.
[ToC:v002/a006]. [ http ] |
| [30] |
R. Raz and A. Shpilka: Deterministic polynomial identity testing in
non-commutative models.
Computational Complexity, 14(1):1-19, 2005.
[CC:p24h4777l51112j8]. |
| [31] |
R. E. Schapire and L. M. Sellie: Learning sparse multivariate polynomials
over a field with queries and counterexamples.
Journal of Computer and System Sciences, 52(2):201-213, 1996.
[JCSS:10.1006/jcss.1996.0017]. |
| [32] |
J. T. Schwartz: Fast probabilistic algorithms for verification of
polynomial identities.
Journal of the ACM, 27(4):701-717, 1980.
[JACM:322217.322225]. |
| [33] |
A. Shpilka and A. Wigderson: Depth-3 arithmetic circuits over fields of
characteristic zero.
Computational Complexity, 10(1):1-27, 2001.
[CC:p8hryxqwkmfr9cm0]. |
| [34] |
M. Sudan, L. Trevisan, and S. P. Vadhan: Pseudorandom generators without
the XOR lemma.
Journal of Computer and System Sciences, 62(2):236-266, 2001.
[JCSS:10.1006/jcss.2000.1730]. |
| [35] |
J. H. van Lint and R. M. Wilson: A Course in Combinatorics.
Cambridge University Press, 2001. |
This file has been generated by bibtex2html 1.81.