{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T11:08:13Z","timestamp":1723806493193},"reference-count":46,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T00:00:00Z","timestamp":1625097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"am","delay-in-days":191,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1618269"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Institut Fran\u00e7ais du Danemark","award":["676541"]},{"name":"CNRS-INS2I Institute"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Symbolic Computation"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1016\/j.jsc.2020.06.006","type":"journal-article","created":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T11:44:18Z","timestamp":1592480658000},"page":"165-198","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":2,"special_numbering":"C","title":["Verification protocols with sub-linear communication for polynomial matrix operations"],"prefix":"10.1016","volume":"105","author":[{"given":"David","family":"Lucas","sequence":"first","affiliation":[]},{"given":"Vincent","family":"Neiger","sequence":"additional","affiliation":[]},{"given":"Cl\u00e9ment","family":"Pernet","sequence":"additional","affiliation":[]},{"given":"Daniel S.","family":"Roche","sequence":"additional","affiliation":[]},{"given":"Johan","family":"Rosenkilde","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.jsc.2020.06.006_br0010","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1137\/S0895479892230031","article-title":"A uniform approach for the fast computation of matrix-type Pad\u00e9 approximants","volume":"15","author":"Beckermann","year":"1994","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"10.1016\/j.jsc.2020.06.006_br0020","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1137\/S0895479897326912","article-title":"Fraction-free computation of matrix rational interpolants and matrix gcds","volume":"22","author":"Beckermann","year":"2000","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"10.1016\/j.jsc.2020.06.006_br0030","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1016\/j.jsc.2006.02.001","article-title":"Normal forms for general polynomial matrices","volume":"41","author":"Beckermann","year":"2006","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.06.006_br0040","doi-asserted-by":"crossref","article-title":"Polynomial and Matrix Computations","author":"Bini","year":"1994","DOI":"10.1007\/978-1-4612-0265-3"},{"key":"10.1016\/j.jsc.2020.06.006_br0050","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1016\/j.jco.2004.09.009","article-title":"Polynomial evaluation and interpolation on special sets of points","volume":"21","author":"Bostan","year":"2005","journal-title":"J. Complex."},{"key":"10.1016\/j.jsc.2020.06.006_br0060","series-title":"Commutative Algebra. Elements of Mathematics","author":"Bourbaki","year":"1972"},{"key":"10.1016\/j.jsc.2020.06.006_br0070","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1007\/BF01178683","article-title":"On fast multiplication of polynomials over arbitrary algebras","volume":"28","author":"Cantor","year":"1991","journal-title":"Acta Inform."},{"key":"10.1016\/j.jsc.2020.06.006_br0080","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith","year":"1990","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.06.006_br0090","series-title":"2015 IEEE Symposium on Security and Privacy","first-page":"253","article-title":"Geppetto: versatile verifiable computation","author":"Costello","year":"2015"},{"key":"10.1016\/j.jsc.2020.06.006_br0100","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","article-title":"A probabilistic remark on algebraic program testing","volume":"7","author":"DeMillo","year":"1978","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.jsc.2020.06.006_br0110","series-title":"Computer Algebra in Scientific Computing","first-page":"1","article-title":"Proof-of-work certificates that can be efficiently computed in the cloud (invited talk)","author":"Dumas","year":"2018"},{"key":"10.1016\/j.jsc.2020.06.006_br0120","series-title":"ISSAC '14","first-page":"146","article-title":"Essentially optimal interactive certificates in linear algebra","author":"Dumas","year":"2014"},{"key":"10.1016\/j.jsc.2020.06.006_br0130","series-title":"ISSAC \u201916","first-page":"199","article-title":"Linear time interactive certificates for the minimal polynomial and the determinant of a sparse matrix","author":"Dumas","year":"2016"},{"key":"10.1016\/j.jsc.2020.06.006_br0140","series-title":"ISSAC \u201917","first-page":"133","article-title":"Certificates for triangular equivalence and rank profiles","author":"Dumas","year":"2017"},{"key":"10.1016\/j.jsc.2020.06.006_br0150","series-title":"ISSAC \u201915","first-page":"149","article-title":"Computing the rank profile matrix","author":"Dumas","year":"2015"},{"key":"10.1016\/j.jsc.2020.06.006_br0160","series-title":"CRYPTO \u201986","first-page":"186","article-title":"How to prove yourself: practical solutions to identification and signature problems","author":"Fiat","year":"1987"},{"key":"10.1016\/j.jsc.2020.06.006_br0170","series-title":"Mathematical Foundations of Computer Science 1979","first-page":"57","article-title":"Fast probabilistic algorithms","author":"Freivalds","year":"1979"},{"key":"10.1016\/j.jsc.2020.06.006_br0180","series-title":"The Theory of Matrices","author":"Gantmacher","year":"1959"},{"key":"10.1016\/j.jsc.2020.06.006_br0190","series-title":"Modern Computer Algebra","author":"von zur Gathen","year":"2013"},{"key":"10.1016\/j.jsc.2020.06.006_br0200","series-title":"ISSAC\u201903","first-page":"135","article-title":"On the complexity of polynomial matrix computations","author":"Giorgi","year":"2003"},{"key":"10.1016\/j.jsc.2020.06.006_br0210","series-title":"ISSAC'18","first-page":"167","article-title":"Certification of minimal approximant bases","author":"Giorgi","year":"2018"},{"key":"10.1016\/j.jsc.2020.06.006_br0220","series-title":"STOC '08","first-page":"113","article-title":"Delegating computation: interactive proofs for muggles","author":"Goldwasser","year":"2008"},{"key":"10.1016\/j.jsc.2020.06.006_br0230","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","article-title":"The knowledge complexity of interactive proof systems","volume":"18","author":"Goldwasser","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jsc.2020.06.006_br0240","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1016\/j.jsc.2011.09.006","article-title":"Triangular x-basis decompositions and derandomization of linear algebra algorithms over K[x]","volume":"47","author":"Gupta","year":"2012","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.06.006_br0250","first-page":"191","article-title":"Sur l'introduction des variables continues dans la th\u00e9orie des nombres","volume":"41","author":"Hermite","year":"1851","journal-title":"J. Reine Angew. Math."},{"key":"10.1016\/j.jsc.2020.06.006_br0260","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.jsc.2013.04.004","article-title":"Rank-profile revealing Gaussian elimination and the CUP matrix decomposition","volume":"56","author":"Jeannerod","year":"2013","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.06.006_br0270","series-title":"Linear Systems","author":"Kailath","year":"1980"},{"key":"10.1016\/j.jsc.2020.06.006_br0280","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jsc.2011.08.002","article-title":"Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients","volume":"47","author":"Kaltofen","year":"2012","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.06.006_br0290","series-title":"ISSAC \u201911","first-page":"171","article-title":"Quadratic-time certificates in linear algebra","author":"Kaltofen","year":"2011"},{"key":"10.1016\/j.jsc.2020.06.006_br0300","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.jco.2017.03.003","article-title":"Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix","volume":"42","author":"Labahn","year":"2017","journal-title":"J. Complex."},{"key":"10.1016\/j.jsc.2020.06.006_br0310","series-title":"ISSAC\u201914","first-page":"296","article-title":"Powers of tensors and fast matrix multiplication","author":"Le Gall","year":"2014"},{"key":"10.1016\/j.jsc.2020.06.006_br0320","series-title":"The Theory of Matrices","author":"MacDuffee","year":"1933"},{"key":"10.1016\/j.jsc.2020.06.006_br0330","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jsc.2003.07.004","article-title":"Certified dense linear system solving","volume":"37","author":"Mulders","year":"2004","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.06.006_br0340","series-title":"ISSAC '18","article-title":"Computing Popov and Hermite forms of rectangular polynomial matrices","author":"Neiger","year":"2018"},{"key":"10.1016\/j.jsc.2020.06.006_br0350","series-title":"ISSAC\u201917","first-page":"357","article-title":"Computing canonical bases of modules of univariate relations","author":"Neiger","year":"2017"},{"key":"10.1016\/j.jsc.2020.06.006_br0360","series-title":"Integral Matrices","volume":"vol. 45","author":"Newman","year":"1972"},{"key":"10.1016\/j.jsc.2020.06.006_br0370","doi-asserted-by":"crossref","first-page":"1675","DOI":"10.1016\/j.jnt.2010.01.017","article-title":"Fast computation of Hermite normal forms of random integer matrices","volume":"130","author":"Pernet","year":"2010","journal-title":"J. Number Theory"},{"key":"10.1016\/j.jsc.2020.06.006_br0380","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/0310020","article-title":"Invariant description of linear, time-invariant controllable systems","volume":"10","author":"Popov","year":"1972","journal-title":"SIAM J. Control"},{"key":"10.1016\/j.jsc.2020.06.006_br0390","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast probabilistic algorithms for verification of polynomial identities","volume":"27","author":"Schwartz","year":"1980","journal-title":"J. ACM"},{"key":"10.1016\/j.jsc.2020.06.006_br0400","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1016\/S0747-7171(03)00097-X","article-title":"High-order lifting and integrality certification","volume":"36","author":"Storjohann","year":"2003","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.06.006_br0410","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/BF02141952","article-title":"A general module theoretic framework for vector M-Pad\u00e9 and matrix rational interpolation","volume":"3","author":"Van Barel","year":"1992","journal-title":"Numer. Algorithms"},{"key":"10.1016\/j.jsc.2020.06.006_br0420","series-title":"ISSAC'96","first-page":"250","article-title":"Computing Popov and Hermite forms of polynomial matrices","author":"Villard","year":"1996"},{"key":"10.1016\/j.jsc.2020.06.006_br0430","series-title":"Fast Order Basis and Kernel Basis Computation and Related Problems","author":"Zhou","year":"2012"},{"key":"10.1016\/j.jsc.2020.06.006_br0440","series-title":"ISSAC'13","first-page":"379","article-title":"Computing column bases of polynomial matrices","author":"Zhou","year":"2013"},{"key":"10.1016\/j.jsc.2020.06.006_br0450","series-title":"ISSAC'14","first-page":"413","article-title":"Unimodular completion of polynomial matrices","author":"Zhou","year":"2014"},{"key":"10.1016\/j.jsc.2020.06.006_br0460","series-title":"EUROSAM'79","first-page":"216","article-title":"Probabilistic algorithms for sparse polynomials","author":"Zippel","year":"1979"}],"container-title":["Journal of Symbolic Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717120300481?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717120300481?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,11,1]],"date-time":"2021-11-01T02:48:15Z","timestamp":1635734895000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0747717120300481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":46,"alternative-id":["S0747717120300481"],"URL":"https:\/\/doi.org\/10.1016\/j.jsc.2020.06.006","relation":{},"ISSN":["0747-7171"],"issn-type":[{"value":"0747-7171","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Verification protocols with sub-linear communication for polynomial matrix operations","name":"articletitle","label":"Article Title"},{"value":"Journal of Symbolic Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jsc.2020.06.006","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2020 Published by Elsevier Ltd.","name":"copyright","label":"Copyright"}]}}
