{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T12:10:33Z","timestamp":1737375033891,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_14","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:26:08Z","timestamp":1187252768000},"page":"176-187","source":"Crossref","is-referenced-by-count":5,"title":["Depth-3 Arithmetic Circuits for S innsu2 (X) and Extensions of the Graham-Pollack Theorem"],"prefix":"10.1007","author":[{"given":"Jaikumar","family":"Radhakrishnan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranab","family":"Sen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sundar","family":"Vishwanathan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01788083","volume":"2","author":"N. Alon","year":"1986","unstructured":"N. Alon. Decomposition of the complete r-graph into complete r-partite r-graphs. Graphs and Combinatorics, 2:95\u2013100, 1986.","journal-title":"Graphs and Combinatorics"},{"key":"14_CR2","unstructured":"L. Babai and P. Frankl. Linear algebra methods in combinatorics (with applications to geometry and computer science). Preliminary Version 2, Department of Computer Science, The University of Chicago, September 1992."},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/0402005","volume":"2","author":"D. Caen de","year":"1989","unstructured":"D. de Caen and D.G. Hoffman. Impossibility of decomposing the complete graph on n points into n-1 isomorphic complete bipartite graphs. SIAM Journal of Discrete Mathematics, 2:48\u201350, 1989.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"R.L. Graham and H.O. Pollack. On embedding graphs in squashed cubes. In Graph Theory and Applications, pages 99\u2013110. Springer-Verlag, 1972. Lecture Notes in Mathematics, 303.","DOI":"10.1007\/BFb0067362"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and M. Karpinski. An exponential lower bound for depth-3 arithmetic circuits. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 577\u2013582, 1998.","DOI":"10.1145\/276698.276872"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and A.A. Razborov. Exponential lower bounds for depth-3 arithmetic circuits in algebras of functions over finite fields. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 269\u2013278, 1998.","DOI":"10.1109\/SFCS.1998.743456"},{"key":"14_CR7","unstructured":"M. Hall jr. Combinatorial Theory. Wiley Interscience series in Discrete Mathematics, 1986."},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"N. Nisan. Lower bounds for non-commutative computation. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 410\u2013418, 1991.","DOI":"10.1145\/103418.103462"},{"key":"14_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01294256","volume":"6","author":"N. Nisan","year":"1996","unstructured":"N. Nisan and A. Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6:217\u2013234, 1996.","journal-title":"Computational Complexity"},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0012-365X(84)90174-2","volume":"49","author":"G.W. Peck","year":"1984","unstructured":"G.W. Peck. A new proof of a theorem of Graham and Pollack. Discrete Mathematics, 49:327\u2013328, 1984.","journal-title":"Discrete Mathematics"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"J. Radhakrishnan, P. Sen, and S. Vishwanathan. Depth-3 arithmetic circuits for S 2 n (X) and extensions of the Graham-Pollack theorem. Full version. Manuscript available at http:\/\/www.tcs.tifr.res.in\/~pranab\/papers\/s2n.ps , September 2000.","DOI":"10.1007\/3-540-44450-5_14"},{"key":"14_CR12","unstructured":"A. Shpilka. Symmetric computation. Manuscript. Personal Communication, January 2000."},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"A. Shpilka and A. Wigderson. Depth-3 arithmetic formulae over fields of characteristic zero. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity, pages 87\u201396, 1999. Also ECCC report no. 23, 1999, available at http:\/\/www.eccc.uni-trier.de\/eccc .","DOI":"10.1109\/CCC.1999.766267"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/jgt.3190060414","volume":"6","author":"H. Tverberg","year":"1982","unstructured":"H. Tverberg. On the decomposition of Kn into complete bipartite graphs. Journal of Graph Theory, 6:493\u2013494, 1982.","journal-title":"Journal of Graph Theory"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T11:30:27Z","timestamp":1737372627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_14","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}