{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004735,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","funder":[{"name":"ERC Starting Grant","award":["101163189"],"award-info":[{"award-number":["101163189"]}]},{"name":"UKRI Future Leaders Fellowship","award":["MR\\\/X023583\\\/1"],"award-info":[{"award-number":["MR\\\/X023583\\\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718128","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"986-994","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Zero-Knowledge PCP Theorem"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7864-7013","authenticated-orcid":false,"given":"Tom","family":"Gur","sequence":"first","affiliation":[{"name":"University of Cambridge, Cambridge, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-2219-599X","authenticated-orcid":false,"given":"Jack","family":"O'Connor","sequence":"additional","affiliation":[{"name":"University of Cambridge, Cambridge, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0085-2137","authenticated-orcid":false,"given":"Nicholas","family":"Spooner","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975498"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585114"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267823"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62223"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70503-3_6"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.27"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30617-4_13"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00077"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511100"},{"key":"e_1_3_2_1_14_1","unstructured":"Alessandro Chiesa Michael A. Forbes and Nicholas Spooner. 2017. A Zero Knowledge Sumcheck and its Applications. IACR Cryptol. ePrint Arch. 305."},{"key":"e_1_3_2_1_15_1","unstructured":"Graham Cormode Marcel Dall\u2019Agnol Tom Gur and Chris Hickey. 2023. Streaming zero-knowledge proofs. arXiv preprint arXiv:2301.02161."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Irit Dinur Ting-Chun Lin and Thomas Vidick. 2024. Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes. arXiv preprint arXiv:2402.07476.","DOI":"10.1109\/FOCS61266.2024.00031"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_3_2_1_19_1","volume-title":"Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Grilo Alex Bredariol","year":"2019","unstructured":"Alex Bredariol Grilo, William Slofstra, and Henry Yuen. 2019. Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE Computer Society, 611\u2013635."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649698"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a018"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-022-09433-3"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_9"},{"key":"e_1_3_2_1_24_1","unstructured":"Yuval Ishai Mohammad Mahmoody Amit Sahai and David Xiao. 2015. On Zero-Knowledge PCPs: Limitations Simplifications and Applications. Available at http:\/\/www.cs.virginia.edu\/ mohammad\/files\/papers\/ZKPCPs-Full.pdf"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Yuval Ishai Amit Sahai Michael Viderman and Mor Weiss. 2013. Zero Knowledge LTCs and Their Applications. In Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and of the 17th International Workshop on Randomization and Computation (APPROX-RANDOM \u201913). 607\u2013622.","DOI":"10.1007\/978-3-642-40328-6_42"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54242-8_6"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49099-0_1"},{"key":"e_1_3_2_1_28_1","volume-title":"Interactive PCP. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP \u201908)","author":"Kalai Yael","year":"2008","unstructured":"Yael Kalai and Ran Raz. 2008. Interactive PCP. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP \u201908). 536\u2013547."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258643"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-02-24-661"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Kieran Mastel and William Slofstra. 2024. Two Prover Perfect Zero Knowledge for MIP. In STOC. ACM 991\u20131002.","DOI":"10.1145\/3618260.3649702"},{"key":"e_1_3_2_1_32_1","volume-title":"Smooth and strong PCPs. computational complexity, 30, 1","author":"Paradise Orr","year":"2021","unstructured":"Orr Paradise. 2021. Smooth and strong PCPs. computational complexity, 30, 1 (2021), 1."},{"key":"e_1_3_2_1_33_1","first-page":"1723","article-title":"Linear-time encodable and decodable error-correcting codes","volume":"42","author":"Spielman Daniel A.","year":"1996","unstructured":"Daniel A. Spielman. 1996. Linear-time encodable and decodable error-correcting codes. ACM Transactions on Internet Technology, 42, 6 (1996), 1723\u20131731. Preliminary version appeared in STOC \u201995.","journal-title":"ACM Transactions on Internet Technology"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.3390\/e24070970"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718128","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:39:36Z","timestamp":1750693176000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":34,"alternative-id":["10.1145\/3717823.3718128","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718128","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}