{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:03Z","timestamp":1763468043121,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642226847"},{"type":"electronic","value":"9783642226854"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22685-4_12","type":"book-chapter","created":{"date-parts":[[2011,8,10]],"date-time":"2011-08-10T08:54:39Z","timestamp":1312966479000},"page":"134-145","source":"Crossref","is-referenced-by-count":3,"title":["Strong I\/O Lower Bounds for Binomial and FFT Computation Graphs"],"prefix":"10.1007","author":[{"given":"Desh","family":"Ranjan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Savage","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Zubair","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"12_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Benhamou, E.: Fast Fourier Transform for discrete Asian options. In: Computing in Economics and Finance. Society for Computational Economics, vol. 6 (April 2001)","DOI":"10.2139\/ssrn.269491"},{"key":"12_CR3","unstructured":"Bezrukov, S.: Edge isoperimetric problems on graphs. Bolyai Math. Series, pp. 157\u2013197."},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Bshouty, N.H.: A lower bound for matrix multiplication. In: FOCS 1988: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 64\u201367 (1988)","DOI":"10.1109\/SFCS.1988.21922"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Carr, P., Madan, D.: Option valuation using the Fast Fourier Transform (1998)","DOI":"10.21314\/JCF.1999.043"},{"issue":"2","key":"12_CR6","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s10878-006-7132-y","volume":"11","author":"Z. Chen","year":"2006","unstructured":"Chen, Z., Fu, B., Tang, Y., Zhu, B.: A ptas for a disc covering problem using width-bounded separators. J. Comb. Optim.\u00a011(2), 203\u2013217 (2006)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"12_CR7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0304-405X(79)90015-1","volume":"7","author":"J.C. Cox","year":"1979","unstructured":"Cox, J.C., Ross, S.A., Rubinstein, M.: Option pricing: A simplified approach. Journal of Financial Economics\u00a07(3), 229\u2013263 (1979)","journal-title":"Journal of Financial Economics"},{"issue":"2","key":"12_CR8","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.jcss.2010.05.003","volume":"77","author":"B. Fu","year":"2011","unstructured":"Fu, B.: Theory and application of width bounded geometric separators. J. Comput. Syst. Sci.\u00a077(2), 379\u2013392 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","volume":"27","author":"W.H. Gates","year":"1979","unstructured":"Gates, W.H., Papadimitriou, C.H.: Bounds for sorting by prefix reversal. Discrete Mathematics\u00a027, 47\u201357 (1979)","journal-title":"Discrete Mathematics"},{"issue":"1","key":"12_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s004540010071","volume":"25","author":"T.C. Hales","year":"2001","unstructured":"Hales, T.C.: The honeycomb conjecture. Discrete & Computational Geometry\u00a025(1), 1\u201322 (2001)","journal-title":"Discrete & Computational Geometry"},{"key":"12_CR11","volume-title":"Computer Architecture: A Quantitative Approach","author":"J.L. Hennessy","year":"2007","unstructured":"Hennessy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco (2007)"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1006\/jagm.1997.0874","volume":"25","author":"M.H. Heydari","year":"1997","unstructured":"Heydari, M.H., Sudborough, I.H.: On the diameter of the pancake network. J. Algorithms\u00a025, 67\u201394 (1997)","journal-title":"J. Algorithms"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Hong, J.-W., Kung, H.T.: I\/O complexity: The red-blue pebble game. In: Proc. 13th Ann. ACM Symp. on Theory of Computing, pp. 326\u2013333 (1981)","DOI":"10.1145\/800076.802486"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: And an\u00a0Overview. Expander graphs and their applications. Bull. Amer. Math. Soc.\u00a043, 439\u2013561 (2006)","journal-title":"Bull. Amer. Math. Soc."},{"key":"12_CR15","volume-title":"Mathematical Models of Financial Derivatives","author":"Y.K. Kwok","year":"1998","unstructured":"Kwok, Y.K.: Mathematical Models of Financial Derivatives. Springer, Singapore (1998)"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Ranjan, D., Savage, J., Zubair, M.: Strong i\/o lower bounds for binomial and fft computation graphs (2011), http:\/\/www.cs.odu.edu\/~zubair\/papers\/ranjanFM11.pdf","DOI":"10.1007\/978-3-642-22685-4_12"},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-19222-7_12","volume-title":"Combinatorial Algorithms","author":"D. Ranjan","year":"2011","unstructured":"Ranjan, D., Savage, J., Zubair, M.: Upper and lower I\/O bounds for pebbling r-pyramids. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol.\u00a06460, pp. 107\u2013120. Springer, Heidelberg (2011)"},{"key":"12_CR18","unstructured":"Ranjan, D., Zubair, M.: Vertex isoperimetric parameter of a computation graph (2010), http:\/\/www.cs.odu.edu\/~zubair\/papers\/hexagonIJFCS.pdf"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/BFb0030842","volume-title":"Computing and Combinatorics","author":"J.E. Savage","year":"1995","unstructured":"Savage, J.E.: Extending the Hong-Kung model to memory hierarchies. In: Du, D.-Z., Li, M. (eds.) Computing and Combinatorics. LNCS, pp. 270\u2013281. Springer, Heidelberg (1995)"},{"key":"12_CR20","volume-title":"Models of Computation: Exploring the Power of Computing","author":"J.E. Savage","year":"1998","unstructured":"Savage, J.E.: Models of Computation: Exploring the Power of Computing. Addison Wesley, Reading (1998)"},{"issue":"1","key":"12_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1644001.1644008","volume":"37","author":"J.E. Savage","year":"2010","unstructured":"Savage, J.E., Zubair, M.: Cache-optimal algorithms for option pricing. ACM Trans. Math. Softw.\u00a037(1), 1\u201330 (2010)","journal-title":"ACM Trans. Math. Softw."},{"key":"12_CR22","unstructured":"Thompson, C.D.: A complexity theory for VLSI. PhD thesis, Pittsburgh, PA, USA (1980)"},{"key":"12_CR23","first-page":"283","volume":"78","author":"J. Yackel","year":"1997","unstructured":"Yackel, J., Meyer, R., Christou, I.: Minimum-perimeter domain assignment. Mathematical Programming\u00a078, 283\u2013303 (1997), doi:10.1007\/BF02614375","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22685-4_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T13:21:59Z","timestamp":1741440119000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22685-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642226847","9783642226854"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22685-4_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}