{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:32:29Z","timestamp":1758709949953,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-1717100"],"award-info":[{"award-number":["CCF-1717100"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,4]]},"DOI":"10.1145\/3476446.3536183","type":"proceedings-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T13:16:01Z","timestamp":1657026961000},"page":"177-186","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The GKR Protocol Revisited"],"prefix":"10.1145","author":[{"given":"Erich L.","family":"Kaltofen","sequence":"first","affiliation":[{"name":"NCSU, Duke University, Raleigh, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215070"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-06-01786-8"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.009"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-06-01837-0"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316380"},{"key":"e_1_3_2_1_6_1","first-page":"57","article-title":"A Zero Knowledge Sumcheck and its Applications","volume":"24","author":"Chiesa Alessandro","year":"2017","unstructured":"Alessandro Chiesa , Michael A. Forbes , and Nicholas Spooner . 2017 . A Zero Knowledge Sumcheck and its Applications . Electron. Colloquium Comput. Complex. , Vol. 24 (2017), 57 . URL: https:\/\/eccc.weizmann.ac.il\/report\/2017\/057 . Alessandro Chiesa, Michael A. Forbes, and Nicholas Spooner. 2017. A Zero Knowledge Sumcheck and its Applications. Electron. Colloquium Comput. Complex., Vol. 24 (2017), 57. URL: https:\/\/eccc.weizmann.ac.il\/report\/2017\/057 .","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090245"},{"key":"e_1_3_2_1_8_1","volume-title":"Essentially Optimal Interactive Certificates In Linear Algebra. In ISSAC 2014 Proc. 39th Internat. Symp. Symbolic Algebraic Comput. , , Katsusuke Nabeshima (Ed.). Association for Computing Machinery","author":"Dumas Jean-Guillaume","year":"2014","unstructured":"Jean-Guillaume Dumas and Erich Kaltofen . 2014 . Essentially Optimal Interactive Certificates In Linear Algebra. In ISSAC 2014 Proc. 39th Internat. Symp. Symbolic Algebraic Comput. , , Katsusuke Nabeshima (Ed.). Association for Computing Machinery , New York, N. Y., 146--153. EKhrefhttp:\/\/users.cs.duke.edu\/ elk27\/bibliography\/14\/DuKa14.pdf EKbib\/14\/DuKa14.pdf . Jean-Guillaume Dumas and Erich Kaltofen. 2014. Essentially Optimal Interactive Certificates In Linear Algebra. In ISSAC 2014 Proc. 39th Internat. Symp. Symbolic Algebraic Comput. , , Katsusuke Nabeshima (Ed.). Association for Computing Machinery, New York, N. Y., 146--153. EKhrefhttp:\/\/users.cs.duke.edu\/ elk27\/bibliography\/14\/DuKa14.pdf EKbib\/14\/DuKa14.pdf ."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2019.07.013"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2930889.2930908"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087640"},{"key":"e_1_3_2_1_12_1","volume-title":"Notes Comput. Sci.","volume":"194","author":"Fiat Amos","year":"1986","unstructured":"Amos Fiat and Adi Shamir . 1986 . How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Advances in Cryptology - CRYPTO'86 (Lect . Notes Comput. Sci. , Vol. 263), A. M. Odlyzko (Ed.). Springer, 186-- 194 . URL: https:\/\/link.springer.com\/chapter\/10.1007\/0--387--34799--2_18 . Amos Fiat and Adi Shamir. 1986. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Advances in Cryptology - CRYPTO'86 (Lect. Notes Comput. Sci., Vol. 263), A. M. Odlyzko (Ed.). Springer, 186--194. URL: https:\/\/link.springer.com\/chapter\/10.1007\/0--387--34799--2_18 ."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680834253"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238185"},{"key":"e_1_3_2_1_15_1","volume-title":"Annual ACM Symp. Theory Comput.","author":"Goldwasser Shafi","year":"2008","unstructured":"Shafi Goldwasser , Yael Tauman Kalai , and Guy N. Rothblum . 2008. Delegating computation: interactive proofs for muggles . In Annual ACM Symp. Theory Comput. 2008 , Cynthia Dwork (Ed.). ACM Press, 113--122. URL: https:doi.acm.org\/10.1145\/1374376.1374396 . Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. 2008. Delegating computation: interactive proofs for muggles. In Annual ACM Symp. Theory Comput. 2008, Cynthia Dwork (Ed.). ACM Press, 113--122. URL: https:doi.acm.org\/10.1145\/1374376.1374396 ."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556789208805505"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2021.193.2.4"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451055"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646660.700858"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0297-x"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26948-7_4"},{"key":"e_1_3_2_1_24_1","volume-title":"Rothblum","author":"Reingold Omer","year":"2016","unstructured":"Omer Reingold , Guy N. Rothblum , and Ron D . Rothblum . 2016 . Constant-Round Interactive Proofs for Delegating Computation. Electronic Colloquium on Comput. Complexity. Report No. 61. URL : https:\/\/eccc.weizmann.ac.il\/report\/2016\/061\/. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. 2016. Constant-Round Interactive Proofs for Delegating Computation. Electronic Colloquium on Comput. Complexity. Report No. 61. URL: https:\/\/eccc.weizmann.ac.il\/report\/2016\/061\/."},{"key":"e_1_3_2_1_25_1","volume-title":"Time-Optimal Interactive Proofs for Circuit Evaluation. In CRYPTO '13 (Lect. Notes Comput. Sci.","volume":"89","author":"Thaler Justin","year":"2013","unstructured":"Justin Thaler . 2013 . Time-Optimal Interactive Proofs for Circuit Evaluation. In CRYPTO '13 (Lect. Notes Comput. Sci. , Vol. 8043), Ran Canetti and Juan A. Garay (Eds.). Springer, 71-- 89 . URL: = https:\/\/doi.org\/10.1007\/978--3--642--40084--1_5 . 10.1007\/978--3--642--40084--1_5 Justin Thaler. 2013. Time-Optimal Interactive Proofs for Circuit Evaluation. In CRYPTO '13 (Lect. Notes Comput. Sci., Vol. 8043), Ran Canetti and Juan A. Garay (Eds.). Springer, 71--89. URL: = https:\/\/doi.org\/10.1007\/978--3--642--40084--1_5 ."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00060"},{"key":"e_1_3_2_1_27_1","volume-title":"Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference","author":"Xie Tiancheng","year":"2019","unstructured":"Tiancheng Xie , Jiaheng Zhang , Yupeng Zhang , Charalampos Papamanthou , and Dawn Song . 2019 . Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference , Santa Barbara, CA, USA , August 18--22, 2019, Proceedings, Part III (Lecture Notes in Computer Science, Vol. 11694), Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, 733-- 764 . URL : https:\/\/doi.org\/10.1007\/978--3-030--26954--8_24 . 10.1007\/978--3-030--26954--8_24 Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. 2019. Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation. In Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18--22, 2019, Proceedings, Part III (Lecture Notes in Computer Science, Vol. 11694), Alexandra Boldyreva and Daniele Micciancio (Eds.). Springer, 733--764. URL: https:\/\/doi.org\/10.1007\/978--3-030--26954--8_24 ."}],"event":{"name":"ISSAC '22: International Symposium on Symbolic and Algebraic Computation","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Villeneuve-d'Ascq France","acronym":"ISSAC '22"},"container-title":["Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3536183","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476446.3536183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:20Z","timestamp":1750268960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3536183"}},"subtitle":["Nearly Optimal Prover-Complexity for Polynomial-Time Wiring Algorithms and for Primality Testing in n1\/2+o(1) Rounds"],"short-title":[],"issued":{"date-parts":[[2022,7,4]]},"references-count":27,"alternative-id":["10.1145\/3476446.3536183","10.1145\/3476446"],"URL":"https:\/\/doi.org\/10.1145\/3476446.3536183","relation":{},"subject":[],"published":{"date-parts":[[2022,7,4]]},"assertion":[{"value":"2022-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}