{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:58:14Z","timestamp":1760061494061,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,7,20]],"date-time":"2016-07-20T00:00:00Z","timestamp":1468972800000},"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":[[2016,7,20]]},"DOI":"10.1145\/2930889.2930908","type":"proceedings-article","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:59:33Z","timestamp":1468929573000},"page":"199-206","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix"],"prefix":"10.1145","author":[{"given":"Jean-Guillaume","family":"Dumas","sequence":"first","affiliation":[{"name":"Universit\u00e9 Grenoble Alpes, Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erich","family":"Kaltofen","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emmanuel","family":"Thom\u00e9","sequence":"additional","affiliation":[{"name":"Inria, Nancy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gilles","family":"Villard","sequence":"additional","affiliation":[{"name":"CNRS, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892230031"},{"key":"e_1_3_2_1_2_1","first-page":"33","volume-title":"CHES 2010","author":"Bertoni G.","year":"2010","unstructured":"G. Bertoni , J. Daemen , M. Peeters , and G. Assche . Sponge-based pseudo-random number generators. In S. Mangard and F.-X. Standaert, editors , CHES 2010 , pages 33 -- 47 . Springer , 2010 . G. Bertoni, J. Daemen, M. Peeters, and G. Assche. Sponge-based pseudo-random number generators. In S. Mangard and F.-X. Standaert, editors, CHES 2010, pages 33--47. Springer, 2010."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(01)00472-4"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"K.-M.\n      Chung Y. T.\n      Kalai and \n      S. P.\n      Vadhan\n  . \n  Improved delegation of computation using fully homomorphic encryption\n  . In T. Rabin editor CRYPTO \n  2010 volume \n  6223\n   of \n  Lecture Notes in Computer Science pages \n  483\n  --\n  501\n  . \n  Springer 2010.   K.-M. Chung Y. T. Kalai and S. P. Vadhan. Improved delegation of computation using fully homomorphic encryption. In T. Rabin editor CRYPTO 2010 volume 6223 of Lecture Notes in Computer Science pages 483--501. Springer 2010.","DOI":"10.1007\/978-3-642-14623-7_26"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/2153413"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_2_1_8_1","volume-title":"Jan.","author":"Dumas J.-G.","year":"2016","unstructured":"J.-G. Dumas , E. Kaltofen , and E. Thom\u00e9 . Certificates for the verification of Wiedemann's Krylov sequence. Technical report, arXiv :, Jan. 2016 . arxiv.org\/abs\/1507.01083. J.-G. Dumas, E. Kaltofen, and E. Thom\u00e9. Certificates for the verification of Wiedemann's Krylov sequence. Technical report, arXiv:, Jan. 2016. arxiv.org\/abs\/1507.01083."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608644"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258776"},{"key":"e_1_3_2_1_11_1","series-title":"Lecture Notes in Computer Science","first-page":"186","volume-title":"Advances in Cryptology - CRYPTO'86","author":"Fiat A.","year":"1986","unstructured":"A. Fiat and A. Shamir . How to prove yourself: Practical solutions to identification and signature problems . In A. M. Odlyzko, editor, Advances in Cryptology - CRYPTO'86 , volume 263 of Lecture Notes in Computer Science , pages 186 -- 194 . Springer , 11-15 Aug. 1986 . A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In A. M. Odlyzko, editor, Advances in Cryptology - CRYPTO'86, volume 263 of Lecture Notes in Computer Science, pages 186--194. Springer, 11-15 Aug. 1986."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382250"},{"key":"e_1_3_2_1_13_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","author":"Freivalds R.","year":"1979","unstructured":"R. Freivalds . Fast probabilistic algorithms . In J. Becv\u00e1r, editor, Mathematical Foundations of Computer Science 1979 , volume 74 of Lecture Notes in Computer Science , pages 57 -- 69 , Olomouc, Czechoslovakia, Sept . 1979. Springer . R. Freivalds. Fast probabilistic algorithms. In J. Becv\u00e1r, editor, Mathematical Foundations of Computer Science 1979, volume 74 of Lecture Notes in Computer Science, pages 57--69, Olomouc, Czechoslovakia, Sept. 1979. Springer."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-014-9184-y"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374396"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/2153451"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/113379.113396"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0185-3"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.08.002"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993886.1993915"},{"key":"e_1_3_2_1_21_1","volume-title":"ISSAC'97","author":"K\u00fcchlin W. W.","year":"1997","unstructured":"W. W. K\u00fcchlin , editor. ISSAC'97 . ACM Press , New York , July 1997 . W. W. K\u00fcchlin, editor. ISSAC'97. ACM Press, New York, July 1997."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670"},{"key":"e_1_3_2_1_23_1","volume-title":"Aug.","author":"NIST.","year":"2015","unstructured":"NIST. FIPS Publication 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions , Aug. 2015 . NIST. FIPS Publication 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, Aug. 2015."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.47"},{"key":"e_1_3_2_1_25_1","first-page":"200","volume-title":"Ng {22}","author":"Schwartz J. T.","unstructured":"J. T. Schwartz . Probabilistic algorithms for verification of polynomial identities. In Ng {22} , pages 200 -- 215 . J. T. Schwartz. Probabilistic algorithms for verification of polynomial identities. In Ng {22}, pages 200--215."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"J.\n      Thaler\n    .\n  Time-optimal interactive proofs for circuit evaluation\n  . In R. Canetti and J. A. Garay editors CRYPTO '13 volume \n  8043\n   of \n  Lecture Notes in Computer Science pages \n  71\n  --\n  89\n  . \n  Springer 2013\n  .  J. Thaler. Time-optimal interactive proofs for circuit evaluation. In R. Canetti and J. A. Garay editors CRYPTO '13 volume 8043 of Lecture Notes in Computer Science pages 71--89. Springer 2013.","DOI":"10.1007\/978-3-642-40084-1_5"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258742"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-57201-2_30"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057137"},{"key":"e_1_3_2_1_30_1","first-page":"216","volume-title":"Ng {22}","author":"Zippel R.","unstructured":"R. Zippel . Probabilistic algorithms for sparse polynomials . In Ng {22} , pages 216 -- 226 . R. Zippel. Probabilistic algorithms for sparse polynomials. In Ng {22}, pages 216--226."}],"event":{"name":"ISSAC '16: International Symposium on Symbolic and Algebraic Computation","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Waterloo ON Canada","acronym":"ISSAC '16"},"container-title":["Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2930889.2930908","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2930889.2930908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:49Z","timestamp":1750222489000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2930889.2930908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,20]]},"references-count":29,"alternative-id":["10.1145\/2930889.2930908","10.1145\/2930889"],"URL":"https:\/\/doi.org\/10.1145\/2930889.2930908","relation":{},"subject":[],"published":{"date-parts":[[2016,7,20]]},"assertion":[{"value":"2016-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}