{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T12:46:45Z","timestamp":1782737205253,"version":"3.54.5"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1933331"],"award-info":[{"award-number":["1933331"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422159"],"award-info":[{"award-number":["CCF-1422159"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2130816"],"award-info":[{"award-number":["CCF-2130816"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF CCF","doi-asserted-by":"publisher","award":["2227876"],"award-info":[{"award-number":["2227876"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF CAREER","doi-asserted-by":"publisher","award":["2239160"],"award-info":[{"award-number":["2239160"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We show that the value of the [Formula: see text]-fold repeated GHZ game is at most [Formula: see text], improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup-type questions from additive combinatorics.<\/jats:p>","DOI":"10.1137\/24m1638124","type":"journal-article","created":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T04:12:26Z","timestamp":1738642346000},"page":"FOCS23-33-FOCS23-41","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Repetition for the GHZ Game: Exponential Decay"],"prefix":"10.1137","volume":"55","author":[{"given":"Mark","family":"Braverman","sequence":"first","affiliation":[{"name":"Department of Computer Science, Princeton University, Princeton, NJ 08540 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhash","family":"Khot","sequence":"additional","affiliation":[{"name":"Courant Institute of Mathematical Sciences, New York University, New York, NY 10012 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dor","family":"Minzer","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,2,4]]},"reference":[{"key":"ref1","unstructured":"A. Bhangale, M. Braverman, S. Khot, Y. P. Liu, and D. Minzer, Parallel Repetition of k-Player Projection Games, Report TR23-198, Electronic Colloquium on Computational Complexity, 2023, https:\/\/eccc.weizmann.ac.il\/report\/2023\/198."},{"key":"ref2","unstructured":"A. Bhangale, M. Braverman, S. Khot, Y. P. Liu, and D. Minzer, Multi-player parallel repetitions theorems beyond XOR games, 2024."},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"A. Bhangale, M. Braverman, S. Khot, Y. P. Liu, and D. Minzer, Parallel Repetition for 3-Player XOR Games, preprint, arXiv:2408.09352, 2024.","DOI":"10.1145\/3717823.3718190"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"A. Bhangale, S. Khot, and D. Minzer, On approximability of satisfiable k-CSPS: I, in STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, 2022, pp. 976\u2013988, https:\/\/doi.org\/10.1145\/3519935.3520028.","DOI":"10.1145\/3519935.3520028"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"M. Braverman and A. Garg, Small value parallel repetition for general games, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, ACM, 2015, pp. 335\u2013340, https:\/\/doi.org\/10.1145\/2746539.2746565.","DOI":"10.1145\/2746539.2746565"},{"key":"ref6","unstructured":"I. Dinur, P. Harsha, R. Venkat, and H. Yuen, Multiplayer parallel repetition for expanding games, in 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, Berkeley, CA, LIPIcs 67, 2017, 37, https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2017.37."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90251-8"},{"key":"ref9","unstructured":"L. J. Fortnow. Complexity-Theoretic Aspects of Interactive Proof Systems, Ph.D. thesis, Citeseer, 1989."},{"key":"ref10","unstructured":"U. Girish, J. Holmgren, K. Mittal, R. Raz, and W. Zhan, Parallel repetition for the GHZ game: A simpler proof, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2021, University of Washington, Seattle, WA (Virtual Conference), LIPIcs 207, 2021, 62, https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2021.62."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520071"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"U. Girish, K. Mittal, R. Raz, and W. Zhan, Polynomial bounds on parallel repetition for all 3-player games with binary inputs, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2022, University of Illinois, Urbana-Champaign, IL (Virtual Conference), LIPIcs 245, 2022, 6, https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2022.6.","DOI":"10.1145\/3519935.3520071"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-001-0332-9"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a008"},{"key":"ref15","unstructured":"J. Holmgren and R. Raz, A Parallel Repetition Theorem for the GHZ Game, CoRR preprint, abs\/2008.05059, 2020, https:\/\/arxiv.org\/abs\/2008.05059."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2818-5"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"H. Pl\u00fcnnecke, Eine zahlentheoretische anwendung der graphentheorie, Journal f\u00fcr die reine und angewandte Mathematik, (1970), https:\/\/doi.org\/10.1515\/crll.1970.243.171.","DOI":"10.1515\/crll.1970.243.171"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/080734042"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"ref20","first-page":"9","volume":"3","author":"Ruzsa I. Z.","year":"1989","journal-title":"Scientia Ser. A"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"A. Samorodnitsky, Low-degree tests at large distances, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007, pp. 506\u2013515.","DOI":"10.1145\/1250790.1250864"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3077-4"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00165-4"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T12:13:26Z","timestamp":1782735206000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1638124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,4]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/24M1638124"],"URL":"https:\/\/doi.org\/10.1137\/24m1638124","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,4]]}}}