{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T18:13:54Z","timestamp":1725732834297},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387081"},{"type":"electronic","value":"9783642387098"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44602-7_11","type":"book-chapter","created":{"date-parts":[[2014,8,23]],"date-time":"2014-08-23T01:18:40Z","timestamp":1408756720000},"page":"123-135","source":"Crossref","is-referenced-by-count":2,"title":["Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds\u2019 Algorithm"],"prefix":"10.1007","author":[{"given":"Ji\u0159\u00ed","family":"Wiedermann","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms, p. 470. Addison-Wesley (1974)"},{"issue":"2","key":"11_CR2","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1137\/100811167","volume":"42","author":"A. De","year":"2013","unstructured":"De, A., Kurur, P.P., Saha, C., Saptharishi, R.: Fast Integer Multiplication Using Modular Arithmetic. SIAM J. Comput.\u00a042(2), 685\u2013699 (2013)","journal-title":"SIAM J. Comput."},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Ar, S., Blum, M., Codenotti, B., Gemmel, P.: Checking approximate computations over the reals. In: Proc. 25th ACM STOC, pp. 786\u2013795 (1993)","DOI":"10.1145\/167088.167288"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation, p. 452. Spinger (1998)","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1016\/S0022-0000(74)80029-2","volume":"8","author":"A. Borodin","year":"1974","unstructured":"Borodin, A., Moenck, R.: Fast modular transform. Journal of Computer and System Sciences\u00a08, 366\u2013386 (1974)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"11_CR6","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.jco.2004.09.009","volume":"21","author":"A. Bostan","year":"2005","unstructured":"Bostan, A., Schost, E.: Polynomial evaluation and interpolation on special sets of points. Journal of Complexity\u00a021(4), 420\u2013446 (2005)","journal-title":"Journal of Complexity"},{"key":"11_CR7","unstructured":"Brassard, G., Bratley, P.: Fundamentals of Algorithmics, 524 pages. Prentice Hall, Englewood Cliffs (1996)"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Buhrman, H., \u0160palek, R.: Quantum verification of matrix products. In: Proceedings of SODA, pp. 880\u2013889 (2006)","DOI":"10.1145\/1109557.1109654"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Cauchy, A.-L.: M\u00e9moire sur la r\u00e9solution num\u00e9rique des \u00e9quations et sur la th\u00e9orie de l\u2019\u00e9limination. Exercices de math\u00e9matiques, 40e et 41e livraisons, dans OC (2), IX, 87\u2013161 (1829)","DOI":"10.1017\/CBO9780511702686.007"},{"key":"11_CR10","unstructured":"Freivalds, R.: Probabilistic machines can use less running time. In: Information Processing 1977, Proceedings of the IFIP Congress 1977, pp. 839\u2013842 (1977)"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Freivalds, R.: Fast Probabilistic Algorithms. In: Be\u010dv\u00e1\u0159, J. (ed.) Mathematical Foundations of Computer Science 1979. LNCS, vol.\u00a079, pp. 57\u201369. Springer, Heidelberg (1979)","DOI":"10.1007\/3-540-09526-8_5"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M.: Faster Integer Multiplication. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13 (2007)","DOI":"10.1145\/1250790.1250800"},{"key":"11_CR13","volume-title":"The Numerical Treatment of a Single Nonlinear Equation","author":"A. Householder","year":"1970","unstructured":"Householder, A.: The Numerical Treatment of a Single Nonlinear Equation. McGraw-Hill, New York (1970)"},{"issue":"2","key":"11_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(93)90224-W","volume":"45","author":"T. Kimbrel","year":"1993","unstructured":"Kimbrel, T., Sinha, R.K.: A probabilistic algorithm for verifying matrix products using O(n 2) time and log2 n\u2009+\u2009O(1) random bits. Inf. Process. Lett.\u00a045(2), 107\u2013110 (1993)","journal-title":"Inf. Process. Lett."},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/978-3-319-04298-5_33","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"I. Korec","year":"2014","unstructured":"Korec, I., Wiedermann, J.: Deterministic verification of integer matrix multiplication in quadratic time. In: Geffert, V., et al. (eds.) SOFSEM 2014. LNCS, vol.\u00a08327, pp. 375\u2013382. Springer, Heidelberg (2014)"},{"key":"11_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-319-08404-6_29","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"F. Gall Le","year":"2014","unstructured":"Le Gall, F., Nishimura, H.: Quantum Algorithms for Matrix Products over Semirings. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol.\u00a08503, pp. 331\u2013343. Springer, Heidelberg (2014)"},{"key":"11_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"issue":"4","key":"11_CR18","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput.\u00a022(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0204018","volume":"4","author":"V. Pratt","year":"1975","unstructured":"Pratt, V.: Every prime has a succinct certificate. SIAM Journal on Computing\u00a04, 214\u2013220 (1975)","journal-title":"SIAM Journal on Computing"},{"issue":"139","key":"11_CR20","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1090\/S0025-5718-1977-0436662-8","volume":"31","author":"F.P. Preparata","year":"1977","unstructured":"Preparata, F.P., Sarwate, D.V.: Computational complexity of Fourier transform over finite fields. Math. of Comp.\u00a031(139), 740\u2013751 (1977)","journal-title":"Math. of Comp."},{"key":"11_CR21","first-page":"181","volume":"11","author":"S. Ramanujan","year":"1919","unstructured":"Ramanujan, S.: A Proof of Bertrand\u2019s Postulate. J. Indian Math. Soc.\u00a011, 181\u2013182 (1919)","journal-title":"J. Indian Math. Soc."},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Raz, R.: On the complexity of matrix product. In: Proc. of the 34th Annual ACM Symposium on Theory of Computing. ACM Press (2002)","DOI":"10.1145\/509907.509932"},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numer. Math.\u00a013, 354\u2013356 (1969)","journal-title":"Numer. Math."},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V.: Multiplying matrices faster than Coppersmith-Winograd. In: ACM STOC, pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"}],"container-title":["Lecture Notes in Computer Science","Advanced Information Systems Engineering"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44602-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T06:36:49Z","timestamp":1565764609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44602-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642387081","9783642387098"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44602-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}