{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:58Z","timestamp":1781077858459,"version":"3.54.1"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,5,24]],"date-time":"2014-05-24T00:00:00Z","timestamp":1400889600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2014,6]]},"DOI":"10.1007\/s00037-014-0085-0","type":"journal-article","created":{"date-parts":[[2014,5,23]],"date-time":"2014-05-23T11:32:19Z","timestamp":1400844739000},"page":"207-303","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Random arithmetic formulas can be reconstructed efficiently"],"prefix":"10.1007","volume":"23","author":[{"given":"Ankit","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Neeraj","family":"Kayal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Youming","family":"Qiao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,5,24]]},"reference":[{"issue":"1","key":"85_CR1","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1137\/060664537","volume":"38","author":"Eric Allender","year":"2008","unstructured":"Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi & Michael E. Saks (2008). Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. SIAM J. Comput. 38(1), 63\u201384.","journal-title":"SIAM J. Comput."},{"key":"85_CR2","unstructured":"Maria Emilia Alonso, Teo Mora & Mario Raimondo (1990). Local Decomposition Algorithms. In AAECC, Shojiro Sakata, editor, volume 508 of Lecture Notes in Computer Science, 208\u2013221. Springer. ISBN 3-540-54195-0."},{"issue":"4","key":"85_CR3","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/s00037-010-0299-8","volume":"19","author":"Vikraman Arvind","year":"2010","unstructured":"Vikraman Arvind, Partha Mukhopadhyay & Srikanth Srinivasan (2010). New Results on Noncommutative and Commutative Polynomial Identity Testing. Computational Complexity 19(4), 521\u2013558.","journal-title":"Computational Complexity"},{"key":"85_CR4","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1090\/S0894-0347-04-00451-5","volume":"7","author":"Matthias Aschenbrenner","year":"2004","unstructured":"Matthias Aschenbrenner (2004). Ideal membership in polynomial rings over the integers. J. Amer. Math. Soc. 7, 407\u2013411.","journal-title":"J. Amer. Math. Soc."},{"issue":"2011","key":"85_CR5","first-page":"785","volume":"20","author":"Matthias Aschenbrenner","year":"2011","unstructured":"Matthias Aschenbrenner (2011). Algorithms for computing saturations of ideals in finitely generated commutative rings: Appendix to: Automorphisms mapping a point into a subvariety, J. Algebraic Geom. 20 (2011), 785-794.","journal-title":"J. Algebraic Geom."},{"key":"85_CR6","doi-asserted-by":"crossref","unstructured":"T. Becker, V. Weispfenning & H. Kredel (1993). Gr\u00f6bner bases: a computational approach to commutative algebra. Graduate texts in mathematics. Springer-Verlag. ISBN 9780387979717. URL http:\/\/books.google.ca\/books?id=qoU_AQAAIAAJ .","DOI":"10.1007\/978-1-4612-0913-3"},{"issue":"3","key":"85_CR7","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/337244.337257","volume":"47","author":"Amos Beimel","year":"2000","unstructured":"Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz & Stefano Varricchio (2000). Learning functions represented as multiplicity automata. J. ACM 47(3), 506\u2013530.","journal-title":"J. ACM"},{"key":"85_CR8","unstructured":"Michael Ben-Or & Prasoon Tiwari (1988). A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation (Extended Abstract). In STOC, Janos Simon, editor, 301\u2013309. ACM. ISBN 0-89791-264-0."},{"issue":"2","key":"85_CR9","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1137\/S009753979528812X","volume":"27","author":"Nader H. Bshouty","year":"1998","unstructured":"Nader H. Bshouty & Richard Cleve (1998). Interpolating Arithmetic Read-Once Formulas in Parallel. SIAM J. Comput. 27(2), 401\u2013413.","journal-title":"SIAM J. Comput."},{"key":"85_CR10","doi-asserted-by":"crossref","unstructured":"Nader H. Bshouty, Richard Cleve & Wayne Eberly (1991). Size-Depth Tradeoffs for Algebraic Formulae. In FOCS, 334\u2013341. IEEE Computer Society.","DOI":"10.1109\/SFCS.1991.185387"},{"key":"85_CR11","unstructured":"David Buchfuhrer & Christopher Umans (2008). The Complexity of Boolean Formula Minimization. In ICALP (1), Luca Aceto, Ivan Damg\u00e5rd, Leslie Ann Goldberg, Magn\u00fas M. Halld\u00f3rsson, Anna Ing\u00f3lfsd\u00f3ttir & Igor Walukiewicz, editors, volume 5125 of Lecture Notes in Computer Science, 24\u201335. Springer. ISBN 978-3-540-70574-1."},{"key":"85_CR12","unstructured":"CCC13 (2013). Proceedings of the 28th Conference on Computational Complexity, CCC 2013, Palo Alto, California, USA, 5-7 June, 2013. IEEE."},{"key":"85_CR13","unstructured":"D.A. Cox, J.B. Little & D. O\u2019Shea (2005). Using algebraic geometry. Graduate texts in mathematics. Springer. ISBN 9780387207063. URL http:\/\/books.google.com\/books?id=1blxizOS9N0C ."},{"key":"85_CR14","doi-asserted-by":"crossref","unstructured":"D.A. Cox, J.B. Little & D. O\u2019Shea (2007). Ideals, Varieties and Algorithms. Undergraduate texts in mathematics. Springer.","DOI":"10.1007\/978-0-387-35651-8"},{"key":"85_CR15","doi-asserted-by":"crossref","unstructured":"Wolfram Decker, Gert-Martin Greuel & Gerhard Pfister(1999). Primary Decomposition: Algorithms and Comparisons. In Algorithmic Algebra and Number Theory, B.Heinrich Matzat, Gert-Martin Greuel & Gerhard Hiss, editors, 187\u2013220. Springer Berlin Heidelberg. ISBN 978-3-540-64670-9. URL http:\/\/dx.doi.org\/10.1007\/978-3-642-59932-3_10 .","DOI":"10.1007\/978-3-642-59932-3_10"},{"key":"85_CR16","doi-asserted-by":"crossref","unstructured":"Thomas W. Dub\u00e9 (1993). A combinatorial proof of the effective Nullstellensatz. J. Symb. Comput. 15, 277\u2013296. ISSN 0747-7171. URL http:\/\/dl.acm.org\/citation.cfm?id=159494.159501 .","DOI":"10.1006\/jsco.1993.1020"},{"issue":"3","key":"85_CR17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1006\/eujc.1993.1022","volume":"14","author":"Richard Ehrenborg","year":"1993","unstructured":"Richard Ehrenborg & Gian-Carlo Rota (1993). Apolarity and Canonical Forms for Homogeneous Polynomials. Eur. J. Comb. 14(3), 157\u2013181.","journal-title":"Eur. J. Comb."},{"key":"85_CR18","unstructured":"Lance Fortnow & Adam R. Klivans (2006). Efficient Learning Algorithms Yield Circuit Lower Bounds. In COLT, G\u00e1bor Lugosi & Hans-Ulrich Simon, editors, volume 4005 of Lecture Notes in Computer Science, 350\u2013363. Springer. ISBN 3-540-35294-5."},{"key":"85_CR19","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0024-3795(87)90337-5","volume":"96","author":"J. zur Gathen von","year":"1987","unstructured":"von zur Gathen J. (1987) Permanent and Determinant. Linear Algebra and its Applications 96: 87\u2013100","journal-title":"Linear Algebra and its Applications"},{"key":"85_CR20","unstructured":"G.M. Greuel & G. Pfister (2007). A Singular Introduction to Commutative Algebra. Springer. ISBN 9783540735427. URL http:\/\/books.google.com.hk\/books?id=7PMdgAPjscsC ."},{"key":"85_CR21","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2013a). Approaching the Chasm at Depth Four. In CCC13 (2013), 65\u201373.","DOI":"10.1109\/CCC.2013.16"},{"key":"85_CR22","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Neeraj Kayal & Satyanarayana V. Lokam (2011). Efficient Reconstruction of Random Multilinear Formulas. In FOCS, Rafail Ostrovsky, editor, 778\u2013787. IEEE. ISBN 978-1-4577-1843-4.","DOI":"10.1109\/FOCS.2011.70"},{"key":"85_CR23","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Neeraj Kayal & Satyanarayana V. Lokam (2012). Reconstruction of depth-4 multilinear circuits with top fan-in 2. In Karloff & Pitassi (2012), 625\u2013642.","DOI":"10.1145\/2213977.2214035"},{"key":"85_CR24","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Neeraj Kayal & Youming Qiao (2013b). Random Arithmetic Formulas Can Be Reconstructed Efficiently. In CCC13 (2013), 1\u20139.","DOI":"10.1109\/CCC.2013.10"},{"key":"85_CR25","unstructured":"Joe Harris (1992). Algebraic Geometry: a first course. Springer."},{"key":"85_CR26","doi-asserted-by":"crossref","unstructured":"Johan H\u00e5stad (1990). Tensor rank is NP-complete. J. Algorithms 11, 644\u2013654. ISSN 0196-6774. URL http:\/\/portal.acm.org\/citation.cfm?id=96134.95990 .","DOI":"10.1016\/0196-6774(90)90014-6"},{"key":"85_CR27","doi-asserted-by":"crossref","unstructured":"Grete Hermann (1926). Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Mathematische Annalen 95, 736\u2013788. ISSN 0025-5831. URL http:\/\/dx.doi.org\/10.1007\/BF01206635 .10.1007\/BF01206635.","DOI":"10.1007\/BF01206635"},{"key":"85_CR28","doi-asserted-by":"crossref","unstructured":"Grete Hermann (1998). The question of finitely many steps in polynomial ideal theory. SIGSAM Bull. 32(3), 8\u201330. ISSN 0163-5824. URL http:\/\/doi.acm.org\/10.1145\/307339.307342 .","DOI":"10.1145\/307339.307342"},{"key":"85_CR29","doi-asserted-by":"crossref","unstructured":"Gabriela Jeronimo & Juan Sabia (2002). Effective equidimensional decomposition of affine varieties. Journal of Pure and Applied Algebra 169(2-3), 229 \u2013 248. ISSN 0022-4049. URL http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022404901000834 .","DOI":"10.1016\/S0022-4049(01)00083-4"},{"key":"85_CR30","doi-asserted-by":"crossref","unstructured":"S. Jukna (2012). Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics. Springer. ISBN 9783642245084. URL http:\/\/books.google.com.sg\/books?id=rHn7hXxyPAkC .","DOI":"10.1007\/978-3-642-24508-4"},{"key":"85_CR31","unstructured":"Valentine Kabanets & Jin-Yi Cai (2000). Circuit minimization problem. In STOC, F. Frances Yao & Eugene M. Luks, editors, 73\u201379. ACM. ISBN 1-58113-184-4."},{"issue":"3","key":"85_CR32","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1137\/0214050","volume":"14","author":"K. Kalorkoti","year":"1985","unstructured":"Kalorkoti K. (1985) A Lower Bound for the Formula Size of Rational Functions. SIAM J. Comput. 14(3): 678\u2013687","journal-title":"SIAM J. Comput."},{"issue":"2","key":"85_CR33","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1137\/0214035","volume":"14","author":"Erich Kaltofen","year":"1985","unstructured":"Erich Kaltofen (1985). Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization. SIAM J. Comput. 14(2), 469\u2013489.","journal-title":"SIAM J. Comput."},{"key":"85_CR34","first-page":"375","volume":"5","author":"Erich Kaltofen","year":"1989","unstructured":"Erich Kaltofen (1989). Factorization of polynomials given by straight-line programs. Randomness and Computation 5, 375\u2013412.","journal-title":"Randomness and Computation"},{"issue":"3","key":"85_CR35","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0747-7171(08)80015-6","volume":"9","author":"Erich Kaltofen","year":"1990","unstructured":"Erich Kaltofen & Barry M. Trager (1990). Computing with Polynomials Given By Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators. J. Symb. Comput. 9(3), 301\u2013320.","journal-title":"J. Symb. Comput."},{"key":"85_CR36","unstructured":"Erich Kaltofen & Lakshman Yagati (1988). Improved Sparse Multivariate Polynomial Interpolation Algorithms. In ISSAC, Patrizia M. Gianni, editor, volume 358 of Lecture Notes in Computer Science, 467\u2013474. Springer. ISBN 3-540-51084-2."},{"key":"85_CR37","unstructured":"Howard J. Karloff & Toniann Pitassi (editors) (2012). Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012. ACM. ISBN 978-1-4503-1245-5."},{"key":"85_CR38","unstructured":"Zohar Shay Karnin & Amir Shpilka (2009). Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. In IEEE Conference on Computational Complexity, 274\u2013285. IEEE Computer Society. ISBN 978-0-7695-3717-7."},{"key":"85_CR39","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal (2011). Efficient algorithms for some special cases of the polynomial equivalence problem. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), 1409\u20131421.","DOI":"10.1137\/1.9781611973082.108"},{"key":"85_CR40","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal (2012). Affine projections of polynomials: extended abstract. In Karloff & Pitassi (2012), 643\u2013662.","DOI":"10.1145\/2213977.2214036"},{"key":"85_CR41","unstructured":"Adam Klivans & Amir Shpilka (2003). Learning Arithmetic Circuits via Partial Derivatives. In COLT, Bernhard Sch\u00f6lkopf & Manfred K. Warmuth, editors, volume 2777 of Lecture Notes in Computer Science, 463\u2013476. Springer. ISBN 3-540-40720-0."},{"key":"85_CR42","unstructured":"Adam Klivans & Daniel A. Spielman (2001). Randomness efficient identity testing of multivariate polynomials. In STOC, Jeffrey Scott Vitter, Paul G. Spirakis & Mihalis Yannakakis, editors, 216\u2013223. ACM. ISBN 1-58113-349-9."},{"key":"85_CR43","unstructured":"Adam R. Klivans, Homin K. Lee & Andrew Wan (2010). Mansour\u2019s Conjecture is True for Random DNF Formulas. In COLT, Adam Tauman Kalai & Mehryar Mohri, editors, 368\u2013380. Omnipress. ISBN 978-0-9822529-2-5."},{"key":"85_CR44","doi-asserted-by":"crossref","first-page":"963","DOI":"10.1090\/S0894-0347-1988-0944576-7","volume":"1","author":"J\u00e1nos Koll\u00e1r","year":"1988","unstructured":"J\u00e1nos Koll\u00e1r (1988). Sharp effective Nullstellensatz. Journal of the American Mathematical Society 1, 963\u2013975.","journal-title":"Journal of the American Mathematical Society"},{"key":"85_CR45","unstructured":"Teresa Krick & Alessandro Logar (1990). Membership problem, representation problem and the computation of the radical for one-dimensional ideals. In Proceedings MEGA-90."},{"key":"85_CR46","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0304-3975(81)90064-5","volume":"15","author":"Daniel Lazard","year":"1981","unstructured":"Daniel Lazard (1981). Resolution des Systemes d\u2019Equations Algebriques. Theor. Comput. Sci. 15, 77\u2013110.","journal-title":"Theor. Comput. Sci."},{"key":"85_CR47","doi-asserted-by":"crossref","unstructured":"Daniel Lazard (2001). Solving systems of algebraic equations. SIGSAM Bull. 35(3), 11\u201337. ISSN 0163-5824. URL http:\/\/doi.acm.org\/10.1145\/569746.569750 .","DOI":"10.1145\/569746.569750"},{"issue":"3","key":"85_CR48","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.jsc.2008.03.004","volume":"44","author":"Daniel Lazard","year":"2009","unstructured":"Daniel Lazard (2009). Thirty years of Polynomial System Solving, and now? J. Symb. Comput. 44(3), 222\u2013231.","journal-title":"Symb. Comput."},{"key":"85_CR49","doi-asserted-by":"crossref","unstructured":"Yishay Mansour (1994). Learning Boolean Functions via the Fourier Transform. In Theoretical Advances in Neural Computation and Learning, 391\u2013424.","DOI":"10.1007\/978-1-4615-2696-4_11"},{"key":"85_CR50","doi-asserted-by":"crossref","unstructured":"Linda Sellie (2009). Exact learning of random DNF formulas over the uniform distribution. In Proceedings of the 41st annual ACM symposium on Theory of computing, STOC \u201909, 45\u201354. ACM, New York, NY, USA. ISBN 978-1-60558-506-2. URL http:\/\/doi.acm.org\/10.1145\/1536414.1536424 .","DOI":"10.1145\/1536414.1536424"},{"issue":"6","key":"85_CR51","doi-asserted-by":"crossref","first-page":"2130","DOI":"10.1137\/070694879","volume":"38","author":"Amir Shpilka","year":"2009","unstructured":"Amir Shpilka (2009). Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. SIAM J. Comput. 38(6), 2130\u20132161.","journal-title":"SIAM J. Comput."},{"key":"85_CR52","unstructured":"Amir Shpilka & Ilya Volkovich (2008). Read-once polynomial identity testing. In STOC, Cynthia Dwork, editor, 507\u2013516. ACM. ISBN 978-1-60558-047-0."},{"key":"85_CR53","doi-asserted-by":"crossref","unstructured":"Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5, 207\u2013388. ISSN 1551-305X. URL http:\/\/dx.doi.org\/10.1561\/0400000039 .","DOI":"10.1561\/0400000039"},{"key":"85_CR54","unstructured":"C.K. Yap (2000). Fundamental problems of algorithmic algebra. Oxford University Press. ISBN 9780195125160. URL http:\/\/books.google.com\/books?id=YzjvQ-TSQ4gC ."},{"issue":"3","key":"85_CR55","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","volume":"9","author":"Richard Zippel","year":"1990","unstructured":"Richard Zippel (1990). Interpolating Polynomials from Their Values. J. Symb. Comput. 9(3), 375\u2013403.","journal-title":"J. Symb. Comput."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0085-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-014-0085-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0085-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T17:32:37Z","timestamp":1565458357000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-014-0085-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,24]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["85"],"URL":"https:\/\/doi.org\/10.1007\/s00037-014-0085-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,24]]}}}