{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:22Z","timestamp":1781028262757,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/Z002230\/1"],"award-info":[{"award-number":["EP\/Z002230\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014037","name":"National Defense Science and Engineering Graduate","doi-asserted-by":"publisher","award":["NDSEG9574PHYSICS"],"award-info":[{"award-number":["NDSEG9574PHYSICS"]}],"id":[{"id":"10.13039\/100014037","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"DOE U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0012704"],"award-info":[{"award-number":["DE-SC0012704"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-2154149"],"award-info":[{"award-number":["CNS-2154149"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800800","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"857-868","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Average-Case Complexity of Quantum Stabilizer Decoding"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8620-4092","authenticated-orcid":false,"given":"Andrey Boris","family":"Khesin","sequence":"first","affiliation":[{"name":"University of Oxford, Computer Science, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2806-8248","authenticated-orcid":false,"given":"Jonathan","family":"Lu","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Mathematics, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7330-1539","authenticated-orcid":false,"given":"Alexander","family":"Poremba","sequence":"additional","affiliation":[{"name":"Boston University, Computer Science, Physics, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9804-5954","authenticated-orcid":false,"given":"Akshar","family":"Ramkumar","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2666-0045","authenticated-orcid":false,"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Computer Science, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359385"},{"key":"e_1_3_2_1_2_1","unstructured":"Dorit Aharonov Michael Ben-Or Elad Eban and Urmila Mahadev. 2017. Interactive Proofs for Quantum Computations. arxiv:1704.04487. arxiv:1704.04487"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.7"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora and Rong Ge. 2011. New algorithms for learning in presence of errors. In International Colloquium on Automata Languages and Programming. 403\u2013415.","DOI":"10.1007\/978-3-642-22006-7_34"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_8_1","unstructured":"H. Barnum and E. Knill. 2000. Reversing quantum dynamics with near-optimal quantum and classical fidelity. arxiv:quant-ph\/0004088. arxiv:quant-ph\/0004088"},{"key":"e_1_3_2_1_9_1","volume-title":"Lipton","author":"Blum Avrim","year":"1994","unstructured":"Avrim Blum, Merrick Furst, Michael Kearns, and Richard J. Lipton. 1994. Cryptographic Primitives Based on Hard Learning Problems. In Advances in Cryptology \u2014 CRYPTO\u2019 93, Douglas R. Stinson (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 278\u2013291. isbn:978-3-540-48329-8"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792543"},{"key":"e_1_3_2_1_11_1","unstructured":"John Bostanci Yuval Efron Tony Metger Alexander Poremba Luowen Qian and Henry Yuen. 2023. Unitary Complexity and the Uhlmann Transformation Problem. arxiv:2306.13073. arxiv:2306.13073"},{"key":"e_1_3_2_1_12_1","unstructured":"Zvika Brakerski Vadim Lyubashevsky Vinod Vaikuntanathan and Daniel Wichs. 2018. Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing. Cryptology ePrint Archive Paper 2018\/279. https:\/\/eprint.iacr.org\/2018\/279"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17659-4_21"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12280-9_10"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_16_1","unstructured":"Yfke Dulek and Florian Speelman. 2018. Quantum ciphertext authentication and key recycling with the trap code. arxiv:1804.02237. arxiv:1804.02237"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.51"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68339-9_22"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91124-8_3"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1952.tb01393.x"},{"key":"e_1_3_2_1_22_1","volume-title":"Matthew JB Robshaw, and Yannick Seurin","author":"Gilbert Henri","year":"2008","unstructured":"Henri Gilbert, Matthew JB Robshaw, and Yannick Seurin. 2008. How to encrypt with the LPN problem. In International Colloquium on Automata, Languages, and Programming. 679\u2013690."},{"key":"e_1_3_2_1_23_1","unstructured":"Daniel Gottesman. 1997. Stabilizer Codes and Quantum Error Correction. arxiv:quant-ph\/9705052. arxiv:quant-ph\/9705052"},{"key":"e_1_3_2_1_24_1","unstructured":"Daniel Gottesman. 2009. An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation. arxiv:0904.2557. arxiv:0904.2557"},{"key":"e_1_3_2_1_25_1","unstructured":"Daniel Gottesman. 2024. Surviving as a Quantum Computer in a Classical World. https:\/\/www.cs.umd.edu\/class\/spring2024\/cmsc858G\/QECCbook-2024-ch1-15.pdf"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132518"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb00463.x"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/jhep06(2013)085"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1088\/1126-6708\/2007\/09\/120"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology (ASIACRYPT \u201901)","author":"Nicholas","unstructured":"Nicholas J. Hopper and Manuel Blum. 2001. Secure Human Identification Protocols. In Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology (ASIACRYPT \u201901). Springer-Verlag, Berlin, Heidelberg. 52\u201366. isbn:3540429875"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.83.052331"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.82"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2422294"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34961-4_40"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_18"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-010-9061-2"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.279.5349.342"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","unstructured":"William Kretschmer. 2021. Quantum Pseudorandomness and Classical Complexity. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPICS.TQC.2021.2 10.4230\/LIPICS.TQC.2021.2","DOI":"10.4230\/LIPICS.TQC.2021.2"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585225"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-020-02622-8"},{"key":"e_1_3_2_1_42_1","volume-title":"Decoding Random Linear Codes, and the Subset Sum Problem","author":"Lyubashevsky Vadim","year":"1874","unstructured":"Vadim Lyubashevsky. 2005. The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, Chandra Chekuri, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Luca Trevisan (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 378\u2013389. isbn:978-3-540-31874-3"},{"key":"e_1_3_2_1_43_1","volume-title":"A Public-Key Cryptosystem Based on Algebraic Coding Theory. Jet Propulsion Laboratory","author":"McEliece Robert J.","unstructured":"Robert J. McEliece. 1978. A Public-Key Cryptosystem Based on Algebraic Coding Theory. Jet Propulsion Laboratory, Pasadena, CA. 114\u2013116."},{"key":"e_1_3_2_1_44_1","unstructured":"Ashley Montanaro. 2019. Pretty simple bounds on quantum state discrimination. arxiv:1908.08312."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2024.4"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27660-6_9"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1960.1057584"},{"key":"e_1_3_2_1_48_1","unstructured":"Alexander Poremba Yihui Quek and Peter Shor. 2025. The Learning Stabilizers with Noise problem. arxiv:2410.18953. arxiv:2410.18953"},{"key":"e_1_3_2_1_49_1","volume-title":"The learning with errors problem. Invited survey in CCC, 7, 30","author":"Regev Oded","year":"2010","unstructured":"Oded Regev. 2010. The learning with errors problem. Invited survey in CCC, 7, 30 (2010), 11."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.R2493"},{"key":"e_1_3_2_1_52_1","volume-title":"Upper and lower bounds on quantum codes. Ph. D. Dissertation","author":"Baird Smith Graeme Stewart","unstructured":"Graeme Stewart Baird Smith. 2006. Upper and lower bounds on quantum codes. Ph. D. Dissertation. California Institute of Technology. USA. isbn:9780542893360 AAI3235592"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48329-2_2"},{"key":"e_1_3_2_1_54_1","volume-title":"Estimation of number of signals in codes with correction of non-symmetric errors. Avtomat. i Telemekh, 25, 11","author":"Varshamov R. R.","year":"1964","unstructured":"R. R. Varshamov. 1964. Estimation of number of signals in codes with correction of non-symmetric errors. Avtomat. i Telemekh, 25, 11 (1964), 1628\u20131629. https:\/\/www.mathnet.ru\/php\/archive.phtml?wshow=paper&jrnid=at&paperid=11783&option_lang=eng"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34621-8_1"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800800","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800800","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:55:21Z","timestamp":1781027721000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800800"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":55,"alternative-id":["10.1145\/3798129.3800800","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800800","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}