{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:10:46Z","timestamp":1737436246965,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540656913"},{"type":"electronic","value":"9783540491163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-49116-3_34","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T12:56:14Z","timestamp":1187268974000},"page":"362-372","source":"Crossref","is-referenced-by-count":2,"title":["Lower Bounds for Dynamic Algebraic Problems"],"prefix":"10.1007","author":[{"given":"Gudmund Skovbjerg","family":"Frandsen","sequence":"first","affiliation":[]},{"given":"Johan P.","family":"Hansen","sequence":"additional","affiliation":[]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,4,12]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Amir M. Ben-Amram and Zvi Galil. Lower bounds for data structure problems on RAMs (extended abstract). In Proc. 32nd Annual Symposium on Foundations of Computer Science, pages 622\u2013631, 1991.","DOI":"10.1109\/SFCS.1991.185428"},{"key":"34_CR2","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1145\/146637.146666","volume":"39","author":"A. M. Ben-Amram","year":"1992","unstructured":"Amir M. Ben-Amram and Zvi Galil. On pointers versus addresses. J. Assoc. Comput. Mach, 39:617\u2013648, 1992.","journal-title":"J. Assoc. Comput. Mach"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0210001","volume":"10","author":"M.L. Fredman","year":"1981","unstructured":"M.L. Fredman. Lower bounds on the complexity of some optimal data structures. SIAM J. Comput., 10:1\u201310, 1981.","journal-title":"SIAM J. Comput."},{"key":"34_CR4","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1145\/322290.322305","volume":"29","author":"M.L. Fredman","year":"1982","unstructured":"M.L. Fredman. The complexity of maintaining an array and computing its partial sums. J. Assoc. Comput. Mach., 29:250\u2013260, 1982.","journal-title":"J. Assoc. Comput. Mach."},{"key":"34_CR5","doi-asserted-by":"crossref","unstructured":"M.L. Fredman and M.E. Saks. The cell probe complexity of dynamic data structures. In Proc. Twenty First Annual ACM Symposium on Theory of Computing, pages 345\u2013354, 1989.","DOI":"10.1145\/73007.73040"},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"M.L. Fredman and D.E. Willard. Surpassing the information-theoretic bound with fusion trees. J. Comput. System Sci., 47:424\u2013436, 1993.","journal-title":"J. Comput. System Sci."},{"key":"34_CR7","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"M.L. Fredman and D.E. Willard. Trans-dichotomous algorithms for mimimum spanning trees and shortest paths. J. Comput. System Sci., 48:533\u2013551, 1994.","journal-title":"J. Comput. System Sci."},{"key":"34_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1007\/BFb0028575","volume-title":"Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science","author":"T. Hagerup","year":"1998","unstructured":"Torben Hagerup. Sorting and searching on the Word RAM. In Proc. 15th Annual Symposium on Theoretical Aspects of Computer Science, LNCS vol. 1373, pages 366\u2013398. Springer-Verlag, 1998."},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"H. Hampapuram and M.L. Fredman. Optimal bi-weighted binary trees and the complexity of maintaining partial sums. In Proc. 34th Annual Symposium on Foundations of Computer Science, pages 480\u2013485, 1993.","DOI":"10.1109\/SFCS.1993.366839"},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"Thomas W. Hungerford. Algebra, volume 73 of Graduate Texts in Mathematics. Springer-Verlag, 1974.","DOI":"10.1007\/978-1-4612-6101-8_4"},{"key":"34_CR11","unstructured":"G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. (Third Edition). Oxford University Press, 1954."},{"key":"34_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0304-3975(84)90032-X","volume":"32","author":"R. Meshulam","year":"1984","unstructured":"Roy Meshulam. A geometric construction of a superconcentrator of depth 2. Theoret. Comput. Sci., 32:215\u2013219, 1984.","journal-title":"Theoret. Comput. Sci."},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. In Proc. 27th Annual ACM Symposium on the Theory of Computing, pages 103\u2013111, 1995.","DOI":"10.1145\/225058.225093"},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"John H. Reif and Stephen R. Tate. On dynamic algorithms for algebraic problems. J. Algorithms, 22:347\u2013371, 1997.","DOI":"10.1006\/jagm.1995.0807"},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"Jaikumar Radhakrishnan and Amnon Ta-Shma. Tight bounds for depth-two superconcentrators. In Proc. 38th Annual Symposium on Foundations of Computer Science, pages 585\u2013594, 1997.","DOI":"10.1109\/SFCS.1997.646148"},{"key":"34_CR16","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1137\/0203011","volume":"3","author":"J.E. Savage","year":"1974","unstructured":"J.E. Savage. An algorithm for the computation of linear forms. SIAM J. Comput., 3:150\u2013158, 1974.","journal-title":"SIAM J. Comput."},{"key":"34_CR17","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant. Graph-theoretic properties in computational complexity. Journal of Computer and System Sciences, 13(3):278\u2013285, December 1976.","DOI":"10.1016\/S0022-0000(76)80041-4"},{"key":"34_CR18","doi-asserted-by":"publisher","first-page":"1840","DOI":"10.1073\/pnas.58.5.1840","volume":"58","author":"S. Winograd","year":"1967","unstructured":"S. Winograd. On the number of multiplications required to compute certain functions. Proc. Nat. Acad. Sci. U.S.A., 58:1840\u20131842, 1967.","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"key":"34_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/cpa.3160230204","volume":"23","author":"S. Winograd","year":"1970","unstructured":"S. Winograd. On the number of multiplications necessary to compute certain functions. Comm. Pure Appl. Math., 23:165\u2013179, 1970.","journal-title":"Comm. Pure Appl. Math."},{"key":"34_CR20","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A.C. Yao","year":"1985","unstructured":"A.C. Yao. On the complexity of maintaining partial sums. SIAM J. Comput., 14:277\u2013288, 1985.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","STACS 99"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49116-3_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T11:45:50Z","timestamp":1737373550000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49116-3_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540656913","9783540491163"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-49116-3_34","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}