{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:46Z","timestamp":1766281006210},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_49","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"581-592","source":"Crossref","is-referenced-by-count":4,"title":["A PCP Characterization of AM"],"prefix":"10.1007","author":[{"given":"Andrew","family":"Drucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"49_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"key":"49_CR2","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. Computational Complexity\u00a03, 319\u2013354 (1993)","journal-title":"Computational Complexity"},{"issue":"4","key":"49_CR3","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.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput.\u00a036(4), 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"key":"49_CR4","doi-asserted-by":"crossref","unstructured":"Condon, A., Feigenbaum, J., Lund, C., Shor, P.S.: Probabilistically checkable debate systems and nonapproximability of PSPACE-hard functions. Chicago J. Theor. Comput. Sci (1995)","DOI":"10.4086\/cjtcs.1995.004"},{"issue":"2","key":"49_CR5","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/S0097539793260738","volume":"26","author":"A. Condon","year":"1997","unstructured":"Condon, A., Feigenbaum, J., Lund, C., Shor, P.S.: Random debaters and the hardness of approximating stochastic functions. SIAM J. Comput.\u00a026(2), 369\u2013400 (1997)","journal-title":"SIAM J. Comput."},{"key":"49_CR6","doi-asserted-by":"crossref","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3) (2007)","DOI":"10.1145\/1236457.1236459"},{"issue":"4","key":"49_CR7","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1137\/S0097539705446962","volume":"36","author":"I. Dinur","year":"2006","unstructured":"Dinur, I., Reingold, O.: Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput.\u00a036(4), 975\u20131024 (2006)","journal-title":"SIAM J. Comput."},{"key":"49_CR8","unstructured":"Drucker, A.: PCPs for Arthur-Merlin Games and Communication Protocols. Master\u2019s thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science (2010)"},{"issue":"1","key":"49_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4086\/toc.2007.v003a003","volume":"3","author":"A. Haviv","year":"2007","unstructured":"Haviv, A., Regev, O., Ta-Shma, A.: On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy. Theory of Computing\u00a03(1), 45\u201360 (2007)","journal-title":"Theory of Computing"},{"issue":"1","key":"49_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00037-007-0238-5","volume":"17","author":"A. Healy","year":"2008","unstructured":"Healy, A.: Randomness-efficient sampling within NC1. Computational Complexity\u00a017(1), 3\u201337 (2008)","journal-title":"Computational Complexity"},{"issue":"4","key":"49_CR11","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1137\/S0097539705447281","volume":"35","author":"A. Healy","year":"2006","unstructured":"Healy, A., Vadhan, S.P., Viola, E.: Using nondeterminism to amplify hardness. SIAM J. Comput.\u00a035(4), 903\u2013931 (2006)","journal-title":"SIAM J. Comput."},{"key":"49_CR12","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: Proc. 36th IEEE FOCS, pp. 538\u2013545 (1995)","DOI":"10.1109\/SFCS.1995.492584"},{"issue":"4","key":"49_CR13","doi-asserted-by":"publisher","first-page":"1637","DOI":"10.1137\/080734030","volume":"39","author":"R. Impagliazzo","year":"2010","unstructured":"Impagliazzo, R., Jaiswal, R., Kabanets, V., Wigderson, A.: Uniform direct product theorems: Simplified, optimized, and derandomized. SIAM J. Comput.\u00a039(4), 1637\u20131665 (2010)","journal-title":"SIAM J. Comput."},{"key":"49_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proc. 29th ACM STOC, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"key":"49_CR15","unstructured":"Ko, K.-I., Lin, C.-C.: Non-approximability in the polynomial-time hierarchy. TR 94-2, Dept. of Computer Science, SUNY at Stony Brook (1994)"},{"issue":"4","key":"49_CR16","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1016\/S0022-0000(02)00022-3","volume":"65","author":"E. Mossel","year":"2002","unstructured":"Mossel, E., Umans, C.: On the complexity of approximating the VC dimension. J. Comput. Syst. Sci.\u00a065(4), 660\u2013671 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"49_CR17","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R.: Hardness amplification within NP. In: Proc. 34th ACM STOC, pp. 751\u2013760 (2002)","DOI":"10.1145\/510014.510015"},{"issue":"3","key":"49_CR18","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1137\/070698348","volume":"39","author":"R. Shaltiel","year":"2009","unstructured":"Shaltiel, R., Umans, C.: Low-end uniform hardness vs. randomness tradeoffs for AM. SIAM J. Comput.\u00a039(3), 1006\u20131037 (2009)","journal-title":"SIAM J. Comput."},{"key":"49_CR19","doi-asserted-by":"crossref","unstructured":"Wigderson, A., Xiao, D.: A randomness-efficient sampler for matrix-valued functions and applications. In: Proc. 46th IEEE FOCS, pp. 397\u2013406 (2005)","DOI":"10.1109\/SFCS.2005.8"},{"issue":"1","key":"49_CR20","doi-asserted-by":"publisher","first-page":"53","DOI":"10.4086\/toc.2008.v004a003","volume":"4","author":"A. Wigderson","year":"2008","unstructured":"Wigderson, A., Xiao, D.: Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. Theory of Computing\u00a04(1), 53\u201376 (2008)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T01:47:54Z","timestamp":1560304074000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}