{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:33:24Z","timestamp":1725798804493},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662447765"},{"type":"electronic","value":"9783662447772"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44777-2_11","type":"book-chapter","created":{"date-parts":[[2014,8,16]],"date-time":"2014-08-16T06:43:15Z","timestamp":1408171395000},"page":"125-136","source":"Crossref","is-referenced-by-count":5,"title":["Polynomial Decompositions in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"11_CR1","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jagm.1994.1005","volume":"16","author":"N. Alon","year":"1994","unstructured":"Alon, N., Duke, R.A., Lefmann, H., R\u00f6dl, V., Yuster, R.: The algorithmic aspects of the regularity lemma. J. Algorithms\u00a016(1), 80\u2013109 (1994)","journal-title":"J. Algorithms"},{"issue":"1","key":"11_CR2","doi-asserted-by":"publisher","first-page":"75","DOI":"10.4086\/toc.2011.v007a006","volume":"7","author":"A. Bhattacharyya","year":"2011","unstructured":"Bhattacharyya, A., Chen, V., Sudan, M., Xie, N.: Testing linear-invariant non-linear properties. Theory Comput\u00a07(1), 75\u201399 (2011)","journal-title":"Theory Comput"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Fischer, E., Hatami, H., Hatami, P., Lovett, S.: Every locally characterized affine-invariant property is testable. In: Proc. 45th Annual ACM Symposium on the Theory of Computing, pp. 429\u2013436 (2013)","DOI":"10.1145\/2488608.2488662"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Fischer, E., Lovett, S.: Testing low complexity affine-invariant properties. In: Proc. 24th ACM-SIAM Symposium on Discrete Algorithms, pp. 1337\u20131355 (2013), \n                  \n                    http:\/\/arxiv.org\/abs\/1201.0330v2","DOI":"10.1137\/1.9781611973105.97"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Shapira, A.: A unified framework for testing linear-invariant properties. In: Proc. 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 478\u2013487 (2010)","DOI":"10.1109\/FOCS.2010.53"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A.: Polynomial decompositions in polynomial time. Technical report (February 2014), \n                  \n                    http:\/\/eccc.hpi-web.de\/report\/2014\/018\/","DOI":"10.1007\/978-3-662-44777-2_11"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Hatami, P., Tulsiani, M.: Algorithmic regularity for polynomials and applications. Technical report (November 2013), \n                  \n                    http:\/\/arxiv.org\/abs\/1311.5090","DOI":"10.1137\/1.9781611973730.125"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Lee, H.K., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R.A., Wan, A.: Testing for concise representations. In: Proc. 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 549\u2013558 (2007)","DOI":"10.1109\/FOCS.2007.32"},{"key":"11_CR9","unstructured":"de Wolf, R.: A Brief Introduction to Fourier Analysis on the Boolean Cube. Graduate Surveys, vol.\u00a01. Theory of Computing Library (2008)"},{"issue":"3","key":"11_CR10","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s000390050065","volume":"8","author":"W.T. Gowers","year":"1998","unstructured":"Gowers, W.T.: A new proof of Szem\u00e9redi\u2019s theorem for arithmetic progressions of length four. Geom. Funct. Anal.\u00a08(3), 529\u2013551 (1998)","journal-title":"Geom. Funct. Anal."},{"issue":"3","key":"11_CR11","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s00039-001-0332-9","volume":"11","author":"W.T. Gowers","year":"2001","unstructured":"Gowers, W.T.: A new proof of Szem\u00e9redi\u2019s theorem. Geom. Funct. Anal.\u00a011(3), 465\u2013588 (2001)","journal-title":"Geom. Funct. Anal."},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1017\/S0013091505000325","volume":"51","author":"B. Green","year":"2008","unstructured":"Green, B., Tao, T.: An inverse theorem for the Gowers U\n                3-norm. Proc. Edin. Math. Soc.\u00a051, 73\u2013153 (2008)","journal-title":"Proc. Edin. Math. Soc."},{"key":"11_CR13","unstructured":"Green, B., Tao, T.: The distribution of polynomials over finite fields, with applications to the Gowers norms. Contrib. Discrete Math.\u00a04(2) (2009)"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"1753","DOI":"10.4007\/annals.2010.171.1753","volume":"171","author":"B. Green","year":"2010","unstructured":"Green, B., Tao, T.: Linear equations in primes. Ann. of Math.\u00a0171, 1753\u20131850 (2010)","journal-title":"Ann. of Math."},{"key":"11_CR15","unstructured":"Green, B., Tao, T., Ziegler, T.: An inverse theorem for the Gowers U\n                \n                  s\u2009+\u20091-norm. In: Ann. of Math. (to appear)"},{"issue":"1","key":"11_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0017089510000546","volume":"53","author":"B. Green","year":"2011","unstructured":"Green, B., Tao, T., Ziegler, T.: An inverse theorem for the Gowers U\n                4-norm. Glasgow Math. J.\u00a053(1), 1\u201350 (2011)","journal-title":"Glasgow Math. J."},{"issue":"1","key":"11_CR17","doi-asserted-by":"publisher","first-page":"397","DOI":"10.4007\/annals.2005.161.397","volume":"161","author":"B. Host","year":"2005","unstructured":"Host, B., Kra, B.: Nonconventional ergodic averages and nilmanifolds. Ann. of Math.\u00a0161(1), 397\u2013488 (2005)","journal-title":"Ann. of Math."},{"issue":"2","key":"11_CR18","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1006\/jcss.1995.1023","volume":"50","author":"E. Kaltofen","year":"1995","unstructured":"Kaltofen, E.: Effective Noether irreducibility forms and applications. J. Comp. Sys. Sci.\u00a050(2), 274\u2013295 (1995)","journal-title":"J. Comp. Sys. Sci."},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Lovett, S.: Worst case to average case reductions for polynomials. In: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 166\u2013175 (2008)","DOI":"10.1109\/FOCS.2008.17"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Karnin, Z.S., Shpilka, A.: Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In: Proc. 24th Annual IEEE Conference on Computational Complexity, pp. 274\u2013285 (2009)","DOI":"10.1109\/CCC.2009.18"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Kopparty, S., Saraf, S., Shpilka, A.: Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization. Technical Report 001, Electronic Colloquium on Computational Complexity (January 2014), \n                  \n                    http:\/\/eccc.hpi-web.de\/report\/2014\/001\/","DOI":"10.1109\/CCC.2014.25"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. on Comput.\u00a0(4), 838\u2013856 (1993), Earlier version in STOC 1990","DOI":"10.1137\/0222053"},{"key":"11_CR23","unstructured":"Szemer\u00e9di, E.: Regular partitions of graphs. In: Bremond, J.C., Fournier, J.C., Las Vergnas, M., Sotteau, D. (eds.) Proc. Colloque Internationaux CNRS 260 \u2013 Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes, pp. 399\u2013401 (1978)"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Tao, T.: Higher Order Fourier Analysis. Graduate Studies in Mathematics, vol.\u00a0142. American Mathematical Society (2012)","DOI":"10.1090\/gsm\/142"},{"issue":"1","key":"11_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2140\/apde.2010.3.1","volume":"3","author":"T. Tao","year":"2010","unstructured":"Tao, T., Ziegler, T.: The inverse conjecture for the Gowers norm over finite fields via the correspondence principle. Analysis & PDE\u00a03(1), 1\u201320 (2010)","journal-title":"Analysis & PDE"},{"issue":"1","key":"11_CR26","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00026-011-0124-3","volume":"16","author":"T. Tao","year":"2012","unstructured":"Tao, T., Ziegler, T.: The inverse conjecture for the Gowers norm over finite fields in low characteristic. Ann. Comb.\u00a016(1), 121\u2013188 (2012)","journal-title":"Ann. Comb."},{"issue":"2","key":"11_CR27","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s00037-009-0273-5","volume":"18","author":"E. Viola","year":"2009","unstructured":"Viola, E.: The sum of D small-bias generators fools polynomials of degree D. Computational Complexity\u00a018(2), 209\u2013217 (2009)","journal-title":"Computational Complexity"},{"issue":"7","key":"11_CR28","doi-asserted-by":"publisher","first-page":"137","DOI":"10.4086\/toc.2008.v004a007","volume":"4","author":"E. Viola","year":"2008","unstructured":"Viola, E., Wigderson, A.: Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory Comput\u00a04(7), 137\u2013168 (2008)","journal-title":"Theory Comput"},{"issue":"171","key":"11_CR29","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1090\/S0025-5718-1985-0790658-X","volume":"45","author":"J. Gathen von zur","year":"1985","unstructured":"von zur Gathen, J., Kaltofen, E.: Factorization of multivariate polynomials over finite fields. Mathematics of Computation\u00a045(171), 251\u2013261 (1985)","journal-title":"Mathematics of Computation"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44777-2_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T12:16:07Z","timestamp":1558959367000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44777-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662447765","9783662447772"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44777-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}