{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T11:38:06Z","timestamp":1770982686388,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["1399\/17"],"award-info":[{"award-number":["1399\/17"]}]},{"name":"Charles University project","award":["UNCE\/SCI\/004,PRIMUS\/17\/SCI\/9"],"award-info":[{"award-number":["UNCE\/SCI\/004,PRIMUS\/17\/SCI\/9"]}]},{"name":"GACR","award":["17-09142S"],"award-info":[{"award-number":["17-09142S"]}]},{"name":"DARPA\/ARL","award":["Safeware Grant W911NF-15-C-0213"],"award-info":[{"award-number":["Safeware Grant W911NF-15-C-0213"]}]},{"name":"Neuron Fund for the support of science"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1414023"],"award-info":[{"award-number":["CNS-1414023"]}],"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":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316400","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"1103-1114","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Finding a Nash equilibrium is no easier than breaking Fiat-Shamir"],"prefix":"10.1145","author":[{"given":"Arka Rai","family":"Choudhuri","sequence":"first","affiliation":[{"name":"Johns Hopkins University, USA"}]},{"given":"Pavel","family":"Hub\u00e1\u010dek","sequence":"additional","affiliation":[{"name":"Charles University in Prague, Czechia"}]},{"given":"Chethan","family":"Kamath","sequence":"additional","affiliation":[{"name":"IST Austria, Austria"}]},{"given":"Krzysztof","family":"Pietrzak","sequence":"additional","affiliation":[{"name":"IST Austria, Austria"}]},{"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[{"name":"IDC Herzliya, Israel"}]},{"given":"Guy N.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Abbot T. Kane D. and Valiant P. On algorithms for Nash equilibria. Unpublished manuscript 2004. http:\/\/web.mit.edu\/tabbott\/Public\/final.pdf. Abbot T. Kane D. and Valiant P. On algorithms for Nash equilibria. Unpublished manuscript 2004. http:\/\/web.mit.edu\/tabbott\/Public\/final.pdf."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055402"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908734"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218053"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090263"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.94"},{"key":"e_1_3_2_1_7_1","unstructured":"Boodaghians S. Kulkarni R. and Mehta R. Nash equilibrium in smoothed polynomial time for network coordination games. CoRR abs\/1809.02280 (2018). Boodaghians S. Kulkarni R. and Mehta R. Nash equilibrium in smoothed polynomial time for network coordination games. CoRR abs\/1809.02280 (2018)."},{"key":"e_1_3_2_1_8_1","unstructured":"STOC \u201919 June 23\u201326 2019 Phoenix AZ USA A.R. Choudhuri P. Hub\u00e1\u010dek C. Kamath K. Pietrzak A. Rosen G.N. Rothblum STOC \u201919 June 23\u201326 2019 Phoenix AZ USA A.R. Choudhuri P. Hub\u00e1\u010dek C. Kamath K. Pietrzak A. Rosen G.N. Rothblum"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9160-8"},{"key":"e_1_3_2_1_10_1","unstructured":"Buresh-Oppenheim J. On the TFNP complexity of factoring. Unpublished http:\/\/www.cs.toronto.edu\/~bureshop\/factor.pdf 2006. Buresh-Oppenheim J. On the TFNP complexity of factoring. Unpublished http:\/\/www.cs.toronto.edu\/~bureshop\/factor.pdf 2006."},{"key":"e_1_3_2_1_12_1","unstructured":"https:\/\/eprint.iacr.org\/2018\/1004. https:\/\/eprint.iacr.org\/2018\/1004."},{"key":"e_1_3_2_1_13_1","first-page":"122","volume-title":"Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 -","author":"Canetti R.","year":"2018"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"https:\/\/eprint.iacr.org\/2018\/1248. https:\/\/eprint.iacr.org\/2018\/1248.","DOI":"10.1002\/ejoc.201701624"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1981-0606517-5"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2001.0728"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133098"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188968"},{"key":"e_1_3_2_1_22_1","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"25","volume-title":"31st Conference on Computational Complexity (CCC 2016) (Dagstuhl","author":"Deng X.","year":"2016"},{"key":"e_1_3_2_1_23_1","series-title":"Lecture Notes in Computer Science","first-page":"194","volume-title":"Advances in Cryptology \u2013 CRYPTO\u201986 (Santa Barbara","author":"Fiat A.","year":"1987"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188880"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53008-5_20"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Goldreich O. Candidate one-way functions based on expander graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad Mihir Bellare Zvika Brakerski Shafi Goldwasser Shai Halevi Tali Kaufman Leonid Levin Noam Nisan Dana Ron Madhu Sudan Luca Trevisan Salil Vadhan Avi Wigderson David Zuckerman. 2011 pp. 76\u201387. Goldreich O. Candidate one-way functions based on expander graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad Mihir Bellare Zvika Brakerski Shafi Goldwasser Shai Halevi Tali Kaufman Leonid Levin Noam Nisan Dana Ron Madhu Sudan Luca Trevisan Salil Vadhan Avi Wigderson David Zuckerman. 2011 pp. 76\u201387.","DOI":"10.1007\/978-3-642-22670-0_10"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238185"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"e_1_3_2_1_30_1","first-page":"21","volume-title":"8th Innovations in Theoretical Computer Science Conference, ITCS 2017","author":"Hub\u00e1\u010dek P.","year":"2017"},{"key":"e_1_3_2_1_31_1","first-page":"1371","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","author":"Hub\u00e1\u010dek P.","year":"2017"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.08.001"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_3_2_1_34_1","first-page":"251","volume-title":"USA","author":"Kalai Y. T.","year":"2017"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/120874655"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.63"},{"key":"e_1_3_2_1_37_1","series-title":"Lecture Notes in Computer Science","first-page":"151","volume-title":"Advances in Cryptology \u2013 EUROCRYPT","author":"Komargodski I.","year":"2017"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.16"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_2_1_44_1","unstructured":"https:\/\/eprint.iacr.org\/2019\/158. https:\/\/eprint.iacr.org\/2019\/158."},{"key":"e_1_3_2_1_45_1","unstructured":"Pietrzak K. Simple verifiable delay functions. IACR Cryptology ePrint Archive 2018 (2018) 627. Pietrzak K. Simple verifiable delay functions. IACR Cryptology ePrint Archive 2018 (2018) 627."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897652"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Rosen A. Segev G. and Shahaf I . Can PPAD hardness be based on standard cryptographic assumptions? In TCC 2017: 15th Theory of Cryptography Conference Part II (Baltimore MD USA Nov. 12\u201315 2017 ) Y. Kalai and L. Reyzin Eds . vol. 10678 of Lecture Notes in Computer Science Springer Heidelberg Germany pp. 747\u2013 776 . Rosen A. Segev G. and Shahaf I. Can PPAD hardness be based on standard cryptographic assumptions? In TCC 2017: 15th Theory of Cryptography Conference Part II (Baltimore MD USA Nov. 12\u201315 2017) Y. Kalai and L. Reyzin Eds. vol. 10678 of Lecture Notes in Computer Science Springer Heidelberg Germany pp. 747\u2013776.","DOI":"10.1007\/978-3-319-70503-3_25"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.28"},{"key":"e_1_3_2_1_50_1","unstructured":"https:\/\/eprint.iacr.org\/2018\/778. https:\/\/eprint.iacr.org\/2018\/778."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316400","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316400","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316400","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:33Z","timestamp":1750204473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316400"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":47,"alternative-id":["10.1145\/3313276.3316400","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316400","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}