{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T08:40:08Z","timestamp":1740300008706,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540407201"},{"type":"electronic","value":"9783540451679"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45167-9_34","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T23:10:53Z","timestamp":1279840253000},"page":"463-476","source":"Crossref","is-referenced-by-count":5,"title":["Learning Arithmetic Circuits via Partial Derivatives"],"prefix":"10.1007","author":[{"given":"Adam R.","family":"Klivans","sequence":"first","affiliation":[]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"34_CR1","first-page":"402","volume-title":"Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing","author":"J. Aspnes","year":"1991","unstructured":"Aspnes, J., Beigel, R., Furst, M., Rudich, S.: The expressive power of voting polynomials. In: Awerbuch, B. (ed.) Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing, pp. 402\u2013409. ACM Press, New York (1991)"},{"issue":"3","key":"34_CR2","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM 45(3), 501\u2013555 (1998)","journal-title":"Journal of the ACM"},{"key":"34_CR3","first-page":"319","volume":"2","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Queries and concept learning. Machine Learning\u00a02, 319 (1987)","journal-title":"Machine Learning"},{"issue":"1","key":"34_CR4","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1006\/jcss.1997.1550","volume":"56","author":"D. Bshouty","year":"1998","unstructured":"Bshouty, D., Bshouty, N.H.: On interpolating arithmetic readonce formulas with exponentiation. Journal of Computer and System Sciences\u00a056(1), 112\u2013124 (1998)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"34_CR5","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/337244.337257","volume":"47","author":"A. Beimel","year":"2000","unstructured":"Beimel, A., Bergadano, F., Bshouty, N.H., Kushilevitz, E., Varricchio, S.: Learning functions represented as multiplicity automata. J. ACM\u00a047(3), 506\u2013530 (2000)","journal-title":"J. ACM"},{"key":"34_CR6","series-title":"LNAI","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/3-540-62685-9_13","volume-title":"Computational Learning Theory","author":"F. Bergadano","year":"1997","unstructured":"Bergadano, F., Bshouty, N.H., Tamon, C., Varricchio, S.: On learning branching programs and small depth circuits. In: Ben-David, S. (ed.) EuroCOLT 1997. LNCS (LNAI), vol.\u00a01208, pp. 150\u2013161. Springer, Heidelberg (1997)"},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"Bshouty, N., Mansour, Y.: Simple learning algorithms for decision trees and multivariate polynomials. SICOMP: SIAM Journal on Computing\u00a031 (2002)","DOI":"10.1137\/S009753979732058X"},{"key":"34_CR8","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1145\/238061.238102","volume-title":"Proc. 9th Annu. Conf. on Comput. Learning Theory","author":"N.H. Bshouty","year":"1996","unstructured":"Bshouty, N.H., Tamon, C., Wilson, D.K.: On learning width two branching programs. In: Proc. 9th Annu. Conf. on Comput. Learning Theory, pp. 224\u2013227. ACM Press, New York (1996)"},{"issue":"1","key":"34_CR9","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/S0022-0000(71)80005-3","volume":"5","author":"J.W. Carlyle","year":"1971","unstructured":"Carlyle, J.W., Paz, A.: Realizations by stochastic finite automata. Journal of Computer and System Sciences\u00a05(1), 26\u201340 (1971)","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR10","first-page":"197","volume":"53","author":"M. Fliess","year":"1974","unstructured":"Fliess, M.: Matrices de Hankel. J. Math. Pures et Appl.\u00a053, 197\u2013224 (1974)","journal-title":"J. Math. Pures et Appl."},{"issue":"1","key":"34_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539791194069","volume":"23","author":"D. Grigoriev","year":"1994","unstructured":"Grigoriev, D., Karpinski, M., Singer, M.F.: Computational complexity of sparse rational interpolation. SIAM Journal on Computing\u00a023(1), 1\u201311 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR12","first-page":"269","volume-title":"39th Annual Symposium on Foundations of Computer Science: proceedings","author":"D. Grigoriev","year":"1998","unstructured":"Grigoriev, D., Razborov, A.A.: Exponential complexity lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. In: IEEE (ed.) 39th Annual Symposium on Foundations of Computer Science: proceedings, Palo Alto, California, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, November 8\u201311, pp. 269\u2013278. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Almost optimal lower bounds for small depth circuits. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, California, May 28-30, pp. 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"Huang, M., Rao, T.: Interpolation of sparse multivariate polynomials over large finite fields with applications. ALGORITHMS: Journal of Algorithms\u00a033 (1999)","DOI":"10.1006\/jagm.1999.1045"},{"key":"34_CR15","doi-asserted-by":"publisher","first-page":"776","DOI":"10.1145\/509907.510018","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002)","author":"J.C. Jackson","year":"2002","unstructured":"Jackson, J.C., Klivans, A.R., Servedio, R.A.: Learnability beyond AC\u00d4. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), New York, May 19\u201321, pp. 776\u2013784. ACM Press, New York (2002)"},{"key":"34_CR16","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1145\/380752.380801","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing: Hersonissos, Crete, Greece","author":"A.R. Klivans","year":"2001","unstructured":"Klivans, A.R., Spielman, D.: Randomness efficient identity testing of multivariate polynomials. In: ACM (ed.) Proceedings of the 33rd Annual ACM Symposium on Theory of Computing: Hersonissos, Crete, Greece, New York, NY, USA, July 6\u20138, pp. 216\u2013223. ACM Press, New York (2001)"},{"issue":"3","key":"34_CR17","first-page":"300","volume":"9","author":"E. Kaltofen","year":"1990","unstructured":"Kaltofen, E., Trager, B.M.: Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. Journal of Symbolic Computation\u00a09(3), 300\u2013320 (301\u2013320) (1990)","journal-title":"Journal of Symbolic Computation"},{"issue":"3","key":"34_CR18","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform and learnability. Journal of the ACM\u00a040(3), 607\u2013620 (1993)","journal-title":"Journal of the ACM"},{"key":"34_CR19","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for non-commutative computation (extended abstract). In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, Louisiana, May 6\u20138, pp. 410\u2013418 (1991)","DOI":"10.1145\/103418.103462"},{"key":"34_CR20","doi-asserted-by":"crossref","unstructured":"Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. CMPCMPL: Computational Complexity\u00a06 (1997)","DOI":"10.1007\/BF01294256"},{"key":"34_CR21","unstructured":"Ohnishi, H., Seki, H., Kasami, T.: A polynomial time learning algorithm for recognizable series. TIEICE: IEICE Transactions on Communications\/ Electronics\/Information and Systems (1994)"},{"issue":"2","key":"34_CR22","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1006\/jcss.1996.0017","volume":"52","author":"R.E. Schapire","year":"1996","unstructured":"Schapire, R.E., Sellie, L.M.: Learning sparse multivariate polynomials over a field with queries and counterexamples. Journal of Computer and System Sciences\u00a052(2), 201\u2013213 (1996)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"34_CR23","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM\u00a027(4), 701\u2013717 (1980)","journal-title":"Journal of the ACM"},{"key":"34_CR24","doi-asserted-by":"crossref","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. JCSS: Journal of Computer and System Sciences\u00a062 (2001)","DOI":"10.1006\/jcss.2000.1730"},{"key":"34_CR25","doi-asserted-by":"crossref","unstructured":"Shpilka, A., Wigderson, A.: Depth-3 arithmetic circuits over fields of characteristic zero. CMPCMPL: Computational Complexity\u00a010 (2001)","DOI":"10.1007\/PL00001609"},{"key":"34_CR26","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072. Springer, Heidelberg (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Lecture Notes in Computer Science","Learning Theory and Kernel Machines"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45167-9_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T07:35:56Z","timestamp":1740296156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45167-9_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407201","9783540451679"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45167-9_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}