{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T12:29:11Z","timestamp":1773145751421,"version":"3.50.1"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319575858","type":"print"},{"value":"9783319575865","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-57586-5_1","type":"book-chapter","created":{"date-parts":[[2017,4,13]],"date-time":"2017-04-13T15:23:34Z","timestamp":1492097014000},"page":"3-9","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["TFNP: An Update"],"prefix":"10.1007","author":[{"given":"Paul W.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,14]]},"reference":[{"issue":"2","key":"1_CR1","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Ann. Math. 160(2), 781\u2013793 (2004)","journal-title":"Ann. Math."},{"key":"1_CR2","unstructured":"Ban, F., Jain, K., Papadimitriou, C.H., Psomas, C.A., Rubinstein, A.: Reductions in PPP. Manuscript (2016)"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Beame, P., Cook, S., Edmonds, J., Impagliazzo, R., Pitassi, T.: The relative complexity of NP search problems. In: 27th ACM Symposium on Theory of Computing, pp. 303\u2013314 (1995)","DOI":"10.1145\/225058.225147"},{"key":"1_CR4","unstructured":"Beckmann, A., Buss, S.: The NP Search Problems of Frege and Extended Frege Proofs, preliminary draft, December 2015"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Paneth, O., Rosen, A.: On the cryptographic hardness of finding a Nash equilibrium. In: FOCS 2015, pp. 1480\u20131498 (2015)","DOI":"10.1109\/FOCS.2015.94"},{"key":"1_CR6","unstructured":"Buss, S.: Bounded Arithmetic, Bibliopolis, Naples, Italy (1986). www.math.ucsd.edu\/~sbuss\/ResearchWeb\/BAthesis\/"},{"issue":"3","key":"1_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 1\u201357 (2009)","journal-title":"J. ACM"},{"issue":"1","key":"1_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Continuous local search. In: SODA 2011, pp. 790\u2013804 (2011)","DOI":"10.1137\/1.9781611973082.62"},{"key":"1_CR10","unstructured":"Filos-Ratsikas, A., Frederiksen, S.K.S., Goldberg, P.W., Zhang, J.: Hardness Results for Consensus-Halving. Corr, arXiv:1609.05136 [cs.GT] (2016)"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/978-3-662-53008-5_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"S Garg","year":"2016","unstructured":"Garg, S., Pandey, O., Srinivasan, A.: Revisiting the cryptographic hardness of finding a Nash equilibrium. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 579\u2013604. Springer, Heidelberg (2016). doi:10.1007\/978-3-662-53008-5_20"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Papadimitriou, C.H.: Towards a Unified Complexity Theory of Total Functions (2017). Submitted","DOI":"10.1016\/j.jcss.2017.12.003"},{"key":"1_CR13","unstructured":"Herbrand, J.: R\u00e9cherches sur la th\u00e9orie de la d\u00e9monstration. Ph.D. thesis, Universit\u00e9 de Paris (1930)"},{"key":"1_CR14","unstructured":"Hub\u00e1\u010dek, P., Naor, M., Yogev, E.: The journey from NP to TFNP hardness. In: 8th ITCS (2017)"},{"issue":"2","key":"1_CR15","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/j.jcss.2015.08.001","volume":"82","author":"E Je\u0159\u00e1bek","year":"2016","unstructured":"Je\u0159\u00e1bek, E.: Integer factoring and modular square roots. J. Comput. Syst. Sci. 82(2), 380\u2013394 (2016)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1_CR16","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Naor, M., Yogev, E.: White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. ECCC Report 15 (2017)","DOI":"10.1109\/FOCS.2017.63"},{"issue":"2","key":"1_CR18","doi-asserted-by":"publisher","first-page":"387","DOI":"10.2178\/jsl\/1082418532","volume":"69","author":"J Kraj\u00ed\u010dek","year":"2004","unstructured":"Kraj\u00ed\u010dek, J.: Implicit proofs. J. Symbolic Logic 69(2), 387\u2013397 (2004)","journal-title":"J. Symbolic Logic"},{"key":"1_CR19","unstructured":"Megiddo, N.: A note on the complexity of $$P$$-matrix LCP and computing an equilibrium. Res. Rep. RJ6439, IBM Almaden Research Center, San Jose, pp. 1\u20135 (1988)"},{"issue":"2","key":"1_CR20","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theoret. Comput. Sci. 81(2), 317\u2013324 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48, 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1007\/s00153-015-0439-6","volume":"54","author":"P Pudl\u00e1k","year":"2015","unstructured":"Pudl\u00e1k, P.: On the complexity of finding falsifying assignments for Herbrand disjunctions. Arch. Math. Logic 54, 769\u2013783 (2015)","journal-title":"Arch. Math. Logic"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Settling the complexity of computing approximate two-player Nash equilibria. In: FOCS (2016)","DOI":"10.1109\/FOCS.2016.35"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Varga, L.: Combinatorial Nullstellensatz modulo prime powers and the parity argument. arXiv:1402.4422 [math.CO] (2014)","DOI":"10.37236\/4124"},{"issue":"3","key":"1_CR25","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1137\/06066775X","volume":"39","author":"S Zhang","year":"2009","unstructured":"Zhang, S.: Tight bounds for randomized and quantum local search. SIAM J. Comput. 39(3), 948\u2013977 (2009)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-57586-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:21:36Z","timestamp":1710346896000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-57586-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319575858","9783319575865"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-57586-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"14 April 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.corelab.ntua.gr\/ciac2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}