{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:27:33Z","timestamp":1762298853043,"version":"3.41.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319996592"},{"type":"electronic","value":"9783319996608"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-319-99660-8_14","type":"book-chapter","created":{"date-parts":[[2018,8,26]],"date-time":"2018-08-26T18:19:21Z","timestamp":1535307561000},"page":"150-162","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Rational Proofs with Strong Utility-Gap Guarantees"],"prefix":"10.1007","author":[{"given":"Jing","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"McCauley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shikha","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,27]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E., Hertrampf, U.: On the power of uniform families of constant depth threshold circuits. In: Symposium on Mathematical Foundations of Computer Science, pp. 158\u2013164 (1990)","DOI":"10.1007\/BFb0029603"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Azar, P.D., Micali, S.: Rational proofs. In: Proceedings of 44th Symposium on Theory of Computing, pp. 1017\u20131028 (2012)","DOI":"10.1145\/2213977.2214069"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Azar, P.D., Micali, S.: Super-efficient rational proofs. In: Proceedings of 14th Conference on Electronic Commerce, pp. 29\u201330 (2013)","DOI":"10.1145\/2492002.2482561"},{"issue":"4","key":"14_CR4","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF01275487","volume":"3","author":"M Bellare","year":"1993","unstructured":"Bellare, M., Goldreich, O., Goldwasser, S.: Randomness in interactive proofs. Comput. Complex. 3(4), 319\u2013354 (1993)","journal-title":"Comput. Complex."},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Short PCPs verifiable in polylogarithmic time. In: Proceedings of Conference on Computational Complexity, pp. 120\u2013134 (2005)","DOI":"10.1109\/CCC.2005.27"},{"issue":"4","key":"14_CR6","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36(4), 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-642-32009-5_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"N Bitansky","year":"2012","unstructured":"Bitansky, N., Chiesa, A.: Succinct arguments from multi-prover interactive proofs and their efficiency benefits. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 255\u2013272. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32009-5_16"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Kadin, J., Thierauf, T.: On functions computable with nonadaptive queries to NP. In: Proceedings of 9th Structure in Complexity Theory Conference, pp. 43\u201352 (1994)","DOI":"10.1109\/SCT.1994.315819"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Campanelli, M., Gennaro, R.: Sequentially composable rational proofs. In: Proceedings of Decision and Game Theory for Security, pp. 270\u2013288 (2015)","DOI":"10.1007\/978-3-319-25594-1_15"},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.ic.2013.03.003","volume":"226","author":"R Canetti","year":"2013","unstructured":"Canetti, R., Riva, B., Rothblum, G.N.: Refereed delegation of computation. Inf. Comput. 226, 16\u201336 (2013)","journal-title":"Inf. Comput."},{"key":"14_CR11","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A., Thaler, J., Venkatasubramanian, S.: Verifiable stream computation and Arthur-Merlin communication. In: Proceedings of Conference on Computational Complexity, pp. 217\u2013243 (2015)"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Stockmeyer, L.J.: Alternation. In: Proceedings of 17th Symposium on Foundations of Computer Science, pp. 98\u2013108 (1976)","DOI":"10.1109\/SFCS.1976.4"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Chen, J., McCauley, S., Singh, S.: Rational proofs with multiple provers. In: Proceedings of 7th Innovations in Theoretical Computer Science Conference, pp. 237\u2013248 (2016)","DOI":"10.1145\/2840728.2840744"},{"key":"14_CR14","unstructured":"Chen, J., McCauley, S., Singh, S.: Rational proofs with non-cooperative provers. arXiv preprint arXiv:1708.00521 (2017)"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Chen, J., McCauley, S., Singh, S.: Efficient Rational Proofs with Strong Utility-Gap Guarantees http:\/\/arxiv.org\/abs\/1807.01389 (2018)","DOI":"10.1007\/978-3-319-99660-8_14"},{"issue":"3","key":"14_CR16","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1006\/jcss.1995.1040","volume":"50","author":"A Condon","year":"1995","unstructured":"Condon, A., Ladner, R.: Interactive proof systems with polynomially bounded strategies. J. Comput. Syst. Sci. 50(3), 506\u2013518 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"14_CR17","doi-asserted-by":"publisher","first-page":"25","DOI":"10.14778\/2047485.2047488","volume":"5","author":"G Cormode","year":"2011","unstructured":"Cormode, G., Thaler, J., Yi, K.: Verifying computations with streaming interactive proofs. Proc. VLDB Endow. 5(1), 25\u201336 (2011)","journal-title":"Proc. VLDB Endow."},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/978-3-662-48971-0_60","volume-title":"Algorithms and Computation","author":"S Daruki","year":"2015","unstructured":"Daruki, S., Thaler, J., Venkatasubramanian, S.: Streaming verification in data analysis. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 715\u2013726. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_60"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J.: Two prover protocols: low error at affordable rates. In: Proceedings of 26th Symposium on Theory of Computing, pp. 172\u2013183 (1994)","DOI":"10.1145\/195058.195128"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J.: Making games short. In: Proceedings of 29th Symposium On Theory of Computing, pp. 506\u2013516 (1997)","DOI":"10.1145\/258533.258644"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Feigenbaum, J., Koller, D., Shor, P.: A game-theoretic classification of interactive complexity classes. In: Proceedings of 10th Structure in Complexity Theory Conference, pp. 227\u2013237 (1995)","DOI":"10.1109\/SCT.1995.514861"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Proceedings of 40th Symposium on Theory of Computing, pp. 113\u2013122 (2008)","DOI":"10.1145\/1374376.1374396"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Guo, S., Hub\u00e1\u010dek, P., Rosen, A., Vald, M.: Rational arguments: single round delegation with sublinear verification. In: Proceedings of 5th Innovations in Theoretical Computer Science, pp. 523\u2013540 (2014)","DOI":"10.1145\/2554797.2554845"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-662-49099-0_12","volume-title":"Theory of Cryptography","author":"S Guo","year":"2016","unstructured":"Guo, S., Hub\u00e1\u010dek, P., Rosen, A., Vald, M.: Rational sumchecks. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 319\u2013351. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_12"},{"issue":"4","key":"14_CR25","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"W Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65(4), 695\u2013716 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR26","unstructured":"Hub\u00e1\u010dek, P.: Rationality in the Cryptographic Model. Ph.D thesis, Department Office Computer Science, Aarhus University (2014)"},{"issue":"11","key":"14_CR27","first-page":"2392","volume":"100","author":"K Inasawa","year":"2017","unstructured":"Inasawa, K., Yasunaga, K.: Rational proofs against rational verifiers. Fundam. Electron. Commun. Comput. Sci. 100(11), 2392\u20132397 (2017)","journal-title":"Fundam. Electron. Commun. Comput. Sci."},{"key":"14_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-662-48000-7_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"YT Kalai","year":"2015","unstructured":"Kalai, Y.T., Rothblum, R.D.: Arguments of proximity. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 422\u2013442. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_21"},{"issue":"4","key":"14_CR29","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1016\/0899-8256(92)90035-Q","volume":"4","author":"D Koller","year":"1992","unstructured":"Koller, D., Megiddo, N.: The complexity of two-person zero-sum games in extensive form. Games Econ. Behav. 4(4), 528\u2013552 (1992)","journal-title":"Games Econ. Behav."},{"issue":"3","key":"14_CR30","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"MW Krentel","year":"1988","unstructured":"Krentel, M.W.: The complexity of optimization problems. J. Comput. Syst. Sci. 36(3), 490\u2013509 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"14_CR31","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"14_CR32","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(84)90034-5","volume":"29","author":"JH Reif","year":"1984","unstructured":"Reif, J.H.: The complexity of two-player games of incomplete information. J. Comput. Syst. Sci. 29(2), 274\u2013301 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR33","doi-asserted-by":"crossref","unstructured":"Rothblum, G.N., Vadhan, S., Wigderson, A.: Interactive proofs of proximity: delegating computation in sublinear time. In: Proceedings of 45th Symposium on Theory of Computing, pp. 793\u2013802 (2013)","DOI":"10.1145\/2488608.2488709"},{"issue":"5","key":"14_CR34","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"KW Wagner","year":"1990","unstructured":"Wagner, K.W.: Bounded query classes. SIAM J. Comput. 19(5), 833\u2013846 (1990)","journal-title":"SIAM J. Comput."},{"key":"14_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-319-13257-0_10","volume-title":"Information Security","author":"Y Zhang","year":"2014","unstructured":"Zhang, Y., Blanton, M.: Efficient secure and verifiable outsourcing of matrix multiplications. In: Chow, S.S.M., Camenisch, J., Hui, L.C.K., Yiu, S.M. (eds.) ISC 2014. LNCS, vol. 8783, pp. 158\u2013178. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-13257-0_10"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-99660-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T15:25:05Z","timestamp":1751815505000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-99660-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319996592","9783319996608"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-99660-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"27 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 September 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 September 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/aims.sjtu.edu.cn\/SAGT_2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}