{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T02:01:31Z","timestamp":1760061691704,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":23,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,7,23]],"date-time":"2014-07-23T00:00:00Z","timestamp":1406073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,7,23]]},"DOI":"10.1145\/2608628.2608644","type":"proceedings-article","created":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T14:23:03Z","timestamp":1404224583000},"page":"146-153","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Essentially optimal interactive certificates in linear algebra"],"prefix":"10.1145","author":[{"given":"Jean-Guillaume","family":"Dumas","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Grenoble, Grenoble, France"}]},{"given":"Erich","family":"Kaltofen","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, NC"}]}],"member":"320","published-online":{"date-parts":[[2014,7,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22192"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34961-4_38"},{"key":"e_1_3_2_1_4_1","first-page":"61","volume-title":"Advances in Cryptology - CRYPTO'82 (23--25","author":"Blum L.","year":"1982","unstructured":"Blum , L. , Blum , M. , and Shub , M . Comparison of two pseudo-random number generators . In Advances in Cryptology - CRYPTO'82 (23--25 Aug. 1982 ), D. Chaum, R. L. Rivest, and A. T. Sherman, Eds., Plenum Press , New York and London, 1983, pp. 61 -- 78 . http:\/\/dx.doi.org\/10.1007\/978-1-4757-0602-4_6. 10.1007\/978-1-4757-0602-4_6 Blum, L., Blum, M., and Shub, M. Comparison of two pseudo-random number generators. In Advances in Cryptology - CRYPTO'82 (23--25 Aug. 1982), D. Chaum, R. L. Rivest, and A. T. Sherman, Eds., Plenum Press, New York and London, 1983, pp. 61--78. http:\/\/dx.doi.org\/10.1007\/978-1-4757-0602-4_6."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"e_1_3_2_1_6_1","volume-title":"Efficient matrix preconditioners for black box linear algebra. Linear Algebra and its Applications 343--344","author":"Chen L.","year":"2002","unstructured":"Chen , L. , Eberly , W. , Kaltofen , E. L. , Saunders , B. D. , Turner , W. J. , and Villard , G . Efficient matrix preconditioners for black box linear algebra. Linear Algebra and its Applications 343--344 ( 2002 ), 119--146. http:\/\/www.math.ncsu.edu\/~kaltofen\/bibliography\/02\/CEKSTV02.pdf. Chen, L., Eberly, W., Kaltofen, E. L., Saunders, B. D., Turner, W. J., and Villard, G. Efficient matrix preconditioners for black box linear algebra. Linear Algebra and its Applications 343--344 (2002), 119--146. http:\/\/www.math.ncsu.edu\/~kaltofen\/bibliography\/02\/CEKSTV02.pdf."},{"key":"e_1_3_2_1_7_1","series-title":"Lecture Notes in Computer Science","first-page":"186","volume-title":"Advances in Cryptology - CRYPTO'86 (11--15","author":"Fiat A.","year":"1986","unstructured":"Fiat , A. , and Shamir , A . How to prove yourself: Practical solutions to identification and signature problems . In Advances in Cryptology - CRYPTO'86 (11--15 Aug. 1986 ), A. M. Odlyzko, Ed ., vol. 263 of Lecture Notes in Computer Science , Springer-Verlag , 1987, pp. 186 -- 194 . http:\/\/www.cs.rit.edu\/~jjk8346\/FiatShamir.pdf. Fiat, A., and Shamir, A. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology - CRYPTO'86 (11--15 Aug. 1986), A. M. Odlyzko, Ed., vol. 263 of Lecture Notes in Computer Science, Springer-Verlag, 1987, pp. 186--194. http:\/\/www.cs.rit.edu\/~jjk8346\/FiatShamir.pdf."},{"key":"e_1_3_2_1_8_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/3-540-69053-0_19","volume-title":"Advances in Cryptology - EUROCRYPT'97","author":"Fischlin R.","year":"1997","unstructured":"Fischlin , R. , and Schnorr , C. P . Stronger security proofs for RSA and Rabin bits . In Advances in Cryptology - EUROCRYPT'97 ( 1997 ), vol. 1233 of Lecture Notes in Computer Science , pp. 267 -- 279 . http:\/\/dx.doi.org\/10.1007\/3-540-69053-0_19. 10.1007\/3-540-69053-0_19 Fischlin, R., and Schnorr, C. P. Stronger security proofs for RSA and Rabin bits. In Advances in Cryptology - EUROCRYPT'97 (1997), vol. 1233 of Lecture Notes in Computer Science, pp. 267--279. http:\/\/dx.doi.org\/10.1007\/3-540-69053-0_19."},{"key":"e_1_3_2_1_9_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/3-540-09526-8_5","volume-title":"Mathematical Foundations of Computer Science 1979 (Olomouc","author":"Freivalds R.","year":"1979","unstructured":"Freivalds , R. Fast probabilistic algorithms . In Mathematical Foundations of Computer Science 1979 (Olomouc , Czechoslovakia, Sept. 1979 ), J. Be\u010dv\u00e1\u0159, Ed., vol. 74 of Lecture Notes in Computer Science , Springer-Verlag , pp. 57 -- 69 . http:\/\/dx.doi.org\/10.1007\/3-540-09526-8_5. 10.1007\/3-540-09526-8_5 Freivalds, R. Fast probabilistic algorithms. In Mathematical Foundations of Computer Science 1979 (Olomouc, Czechoslovakia, Sept. 1979), J. Be\u010dv\u00e1\u0159, Ed., vol. 74 of Lecture Notes in Computer Science, Springer-Verlag, pp. 57--69. http:\/\/dx.doi.org\/10.1007\/3-540-09526-8_5."},{"key":"e_1_3_2_1_10_1","first-page":"429","volume-title":"On completeness and soundness in interactive proof systems","author":"Furer M.","year":"1989","unstructured":"Furer , M. , Goldreich , O. , Mansour , Y. , Sipser , M. , and Zachos , S . On completeness and soundness in interactive proof systems . In Randomness and Computation, S. Micali, Ed., vol. 5 . Advances in Computing Research, JAI Press , Greenwich, Connecticut, 1989 , pp. 429 -- 442 . http:\/\/www.wisdom.weizmann.ac.il\/~oded\/PS\/fgmsz.ps. Furer, M., Goldreich, O., Mansour, Y., Sipser, M., and Zachos, S. On completeness and soundness in interactive proof systems. In Randomness and Computation, S. Micali, Ed., vol. 5. Advances in Computing Research, JAI Press, Greenwich, Connecticut, 1989, pp. 429--442. http:\/\/www.wisdom.weizmann.ac.il\/~oded\/PS\/fgmsz.ps."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/281508.281591"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374396"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22178"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.08.002"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993886.1993915"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90224-W"},{"key":"e_1_3_2_1_17_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/3-540-68339-9_33","volume-title":"Advances in Cryptology - EUROCRYPT'96 (12--16","author":"Pointcheval D.","year":"1996","unstructured":"Pointcheval , D. , and Stern , J . Security proofs for signature schemes . In Advances in Cryptology - EUROCRYPT'96 (12--16 May 1996 ), U. Maurer, Ed ., vol. 1070 of Lecture Notes in Computer Science , Springer-Verlag , pp. 387 -- 398 . http:\/\/www.di.ens.fr\/~pointche\/Documents\/Papers\/1996_eurocrypt.pdf. Pointcheval, D., and Stern, J. Security proofs for signature schemes. In Advances in Cryptology - EUROCRYPT'96 (12--16 May 1996), U. Maurer, Ed., vol. 1070 of Lecture Notes in Computer Science, Springer-Verlag, pp. 387--398. http:\/\/www.di.ens.fr\/~pointche\/Documents\/Papers\/1996_eurocrypt.pdf."},{"key":"e_1_3_2_1_18_1","first-page":"3","volume":"4","author":"Pratt V. R.","year":"1975","unstructured":"Pratt , V. R. Every prime has a succinct certificate. SIAM Journal on Computing 4 , 3 ( Sept. 1975 ), 214--220. http:\/\/boole.stanford.edu\/pub\/SucCert.pdf. Pratt, V. R. Every prime has a succinct certificate. SIAM Journal on Computing 4, 3 (Sept. 1975), 214--220. http:\/\/boole.stanford.edu\/pub\/SucCert.pdf.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.13001\/1081-3810.1118"},{"key":"e_1_3_2_1_20_1","volume-title":"Ed. STOC '85, ACM Symposium on Theory of Computing","author":"Sedgewick R.","year":"1985","unstructured":"Sedgewick , R. , Ed. STOC '85, ACM Symposium on Theory of Computing , Providence, Rhode Island, USA ( May 1985 ), ACM Press, New York. Sedgewick, R., Ed. STOC '85, ACM Symposium on Theory of Computing, Providence, Rhode Island, USA (May 1985), ACM Press, New York."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1576702.1576748"},{"key":"e_1_3_2_1_22_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/978-3-642-40084-1_5","volume-title":"Advances in Cryptology - CRYPTO'13","author":"Thaler J.","year":"2013","unstructured":"Thaler , J. Time-optimal interactive proofs for circuit evaluation . In Advances in Cryptology - CRYPTO'13 ( 2013 ), R. Canetti and J. Garay, Eds ., vol. 8043 of Lecture Notes in Computer Science , Springer Berlin Heidelberg , pp. 71 -- 89 . http:\/\/arxiv.org\/abs\/1304.3812. Thaler, J. Time-optimal interactive proofs for circuit evaluation. In Advances in Cryptology - CRYPTO'13 (2013), R. Canetti and J. Garay, Eds., vol. 8043 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, pp. 71--89. http:\/\/arxiv.org\/abs\/1304.3812."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057137"}],"event":{"name":"ISSAC '14: International Symposium on Symbolic and Algebraic Computation","sponsor":["ACM Association for Computing Machinery","SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Kobe Japan","acronym":"ISSAC '14"},"container-title":["Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2608628.2608644","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2608628.2608644","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:55:59Z","timestamp":1750272959000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2608628.2608644"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,23]]},"references-count":23,"alternative-id":["10.1145\/2608628.2608644","10.1145\/2608628"],"URL":"https:\/\/doi.org\/10.1145\/2608628.2608644","relation":{},"subject":[],"published":{"date-parts":[[2014,7,23]]},"assertion":[{"value":"2014-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}