[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 AC⁰. 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].

[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.

[36]   R. Zippel: Probabilistic algorithms for sparse polynomials. In Proc. Intern. Symp. on Symbolic and Algebraic Manipulation, volume 72 of Lecture Notes in Computer Science, pp. 216–226. Springer, 1979. [LNCS:y1157233175643jq].