{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:30:59Z","timestamp":1725798659598},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_16","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:33:02Z","timestamp":1407839582000},"page":"177-188","source":"Crossref","is-referenced-by-count":0,"title":["On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields"],"prefix":"10.1007","author":[{"given":"Suryajith","family":"Chillara","sequence":"first","affiliation":[]},{"given":"Partha","family":"Mukhopadhyay","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N.: Combinatorial nullstellensatz. Combinatorics, Probability and Computing\u00a08 (1999)","DOI":"10.1017\/S0963548398003411"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, M.: V\u00a0Vinay. Arithmetic circuits: A chasm at depth four. In: Proceedings-Annual Symposium on Foundations of Computer Science, pp. 67\u201375. IEEE (2008)","DOI":"10.1109\/FOCS.2008.32"},{"key":"16_CR3","unstructured":"Chillara, S.: (2014), \n                    \n                      http:\/\/www.cmi.ac.in\/~suryajith\/Depth3.pdf"},{"key":"16_CR4","unstructured":"Chillara, S., Mukhopadhyay, P.: Depth-4 lower bounds, determinantal complexity: A unified approach. In: STACS, pp. 239\u2013250 (2014)"},{"key":"16_CR5","unstructured":"Feige, U.: The permanent and the determinant (2009)"},{"issue":"1","key":"16_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.2307\/2690560","volume":"67","author":"I. Fischer","year":"1994","unstructured":"Fischer, I.: Sums of like powers of multivariate linear forms. Mathematics Magazine\u00a067(1), 59\u201361 (1994)","journal-title":"Mathematics Magazine"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Fournier, H., Limaye, N., Malod, G., Srinivasan, S.: Lower bounds for depth 4 formulas computing iterated matrix multiplication. In: To Appear in the proceedings of STOC 2014. Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a020, p. 100 (2013)","DOI":"10.1145\/2591796.2591824"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M.: An exponential lower bound for depth 3 arithmetic circuits. In: STOC, pp. 577\u2013582 (1998)","DOI":"10.1145\/276698.276872"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Approaching the chasm at depth four. In: IEEE Conference on Computational Complexity, pp. 65\u201373 (2013)","DOI":"10.1109\/CCC.2013.16"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Arithmetic circuits: A chasm at depth three. In: FOCS, pp. 578\u2013587 (2013)","DOI":"10.1109\/FOCS.2013.68"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Kayal, N., Limaye, N., Saha, C., Srinivasan, S.: An exponential lower bound for homogeneous depth four arithmetic formulas. In: To appear in the Proceedings of STOC 2014. Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a021, p. 5 (2014)","DOI":"10.1109\/FOCS.2014.15"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/978-3-642-39206-1_56","volume-title":"Automata, Languages, and Programming","author":"M. Kumar","year":"2013","unstructured":"Kumar, M., Maheshwari, G., Sarma M.N., J.: Arithmetic circuit lower bounds via maxRank. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 661\u2013672. Springer, Heidelberg (2013)"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2012.03.041","volume":"448","author":"P. Koiran","year":"2012","unstructured":"Koiran, P.: Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci.\u00a0448, 56\u201365 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Kumar, M., Saraf, S.: The limits of depth reduction for arithmetic formulas: It\u2019s all about the top fan-in. In: To appear in the Proceedings of STOC 2014. Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a020, p. 153 (2013)","DOI":"10.1145\/2591796.2591827"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1007\/978-3-662-43948-7_62","volume-title":"Automata, Languages, and Programming","author":"M. Kumar","year":"2014","unstructured":"Kumar, M., Saraf, S.: Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol.\u00a08572, pp. 751\u2013762. Springer, Heidelberg (2014)"},{"key":"16_CR16","first-page":"45","volume":"21","author":"M. Kumar","year":"2014","unstructured":"Kumar, M., Saraf, S.: On the power of homogeneous depth 4 arithmetic circuits. Electronic Colloquium on Computational Complexity (ECCC)\u00a021, 45 (2014)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Kayal, N., Saha, C., Saptharishi, R.: A super-polynomial lower bound for regular arithmetic formulas. In: To appear in the Proceedings of STOC 2014. Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a020, p. 91 (2013)","DOI":"10.1145\/2591796.2591847"},{"issue":"4","key":"16_CR18","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete mathematics\u00a013(4), 383\u2013390 (1975)","journal-title":"Discrete mathematics"},{"issue":"2","key":"16_CR19","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci.\u00a049(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"16_CR20","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01294256","volume":"6","author":"N. Nisan","year":"1997","unstructured":"Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity\u00a06(3), 217\u2013234 (1997)","journal-title":"Computational Complexity"},{"key":"16_CR21","unstructured":"Saptharishi, R.: Personal communication (2013)"},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/978-3-540-70575-8_6","volume-title":"Automata, Languages and Programming","author":"N. Saxena","year":"2008","unstructured":"Saxena, N.: Diagonal circuit identity testing and lower bounds. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 60\u201371. Springer, Heidelberg (2008)"},{"issue":"1","key":"16_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00001609","volume":"10","author":"A. Shpilka","year":"2001","unstructured":"Shpilka, A., Wigderson, A.: Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity\u00a010(1), 1\u201327 (2001)","journal-title":"Computational Complexity"},{"key":"16_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1007\/978-3-642-40313-2_71","volume-title":"Mathematical Foundations of Computer Science 2013","author":"S. Tavenas","year":"2013","unstructured":"Tavenas, S.: Improved bounds for reduction to depth 4 and depth 3. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol.\u00a08087, pp. 813\u2013824. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T15:17:45Z","timestamp":1558970265000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}