{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T22:45:25Z","timestamp":1648766725417},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,6,18]],"date-time":"2013-06-18T00:00:00Z","timestamp":1371513600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,9]]},"DOI":"10.1007\/s00037-013-0071-y","type":"journal-article","created":{"date-parts":[[2013,6,17]],"date-time":"2013-06-17T08:30:56Z","timestamp":1371457856000},"page":"565-594","source":"Crossref","is-referenced-by-count":3,"title":["Derandomized Parallel Repetition Theorems for Free Games"],"prefix":"10.1007","volume":"22","author":[{"given":"Ronen","family":"Shaltiel","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,6,18]]},"reference":[{"key":"71_CR1","doi-asserted-by":"crossref","unstructured":"Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev & David Steurer (2008). Rounding Parallel Repetitions of Unique Games. In FOCS, 374\u2013383.","DOI":"10.1109\/FOCS.2008.55"},{"key":"71_CR2","doi-asserted-by":"crossref","unstructured":"Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen & Ronen Shaltiel (2009). Strong Parallel Repetition Theorem for Free Projection Games. In APPROX-RANDOM, 352\u2013365.","DOI":"10.1007\/978-3-642-03685-9_27"},{"key":"71_CR3","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF01275487","volume":"3","author":"Mihir Bellare","year":"1993","unstructured":"Mihir Bellare, Oded Goldreich, Shafi Goldwasser (1993) Randomness in Interactive Proofs. Computational Complexity 3: 319\u2013354","journal-title":"Computational Complexity"},{"key":"71_CR4","doi-asserted-by":"crossref","unstructured":"Michael Ben-Or, Shafi Goldwasser, Joe Kilian & Avi Wigderson (1988). Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions. In STOC, 113\u2013131.","DOI":"10.1145\/62212.62223"},{"key":"71_CR5","doi-asserted-by":"crossref","unstructured":"Uriel Feige (1991). On the Success Probability of the Two Provers in One-Round Proof Systems. In Structure in Complexity Theory Conference, 116\u2013123.","DOI":"10.1109\/SCT.1991.160251"},{"key":"71_CR6","unstructured":"Uriel Feige (1995). Error reduction by parallel repetition-the state of the art. Technical report, Weizmann Institute, Jerusalem, Israel."},{"key":"71_CR7","unstructured":"Uriel Feige & Joe Kilian (1995). Impossibility results for recycling random bits in two-prover proof systems. In STOC, 457\u2013468."},{"issue":"4","key":"71_CR8","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s00493-002-0001-0","volume":"22","author":"Uriel Feige","year":"2002","unstructured":"Uriel Feige, Oleg Verbitsky (2002) Error Reduction by Parallel Repetition - A Negative Result. Combinatorica 22(4): 461\u2013478","journal-title":"Combinatorica"},{"key":"71_CR9","unstructured":"Lance Fortnow, John Rompel & Michael Sipser (1990). Errata for On the Power of Multi-Prover Interactive Protocols. In Structure in Complexity Theory Conference, 318\u2013319."},{"key":"71_CR10","unstructured":"Oded Goldreich (1997). A Sample of Samplers - A Computational Perspective on Sampling (survey). Electronic Colloquium on Computational Complexity (ECCC) 4(20)."},{"key":"71_CR11","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Russell Impagliazzo, Leonid Levin, Venkatesan Ramarathanan & David Zuckerman (1990). Security Preserving Amplification of Hardness. In FOCS, 318\u2013326.","DOI":"10.1109\/FSCS.1990.89550"},{"key":"71_CR12","unstructured":"Oded Goldreich, Noam Nisan & Avi Wigderson (1995). On Yao\u2019s XOR-Lemma. Electronic Colloquium on Computational Complexity (ECCC) 2(50)."},{"key":"71_CR13","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami, Christopher Umans & Salil P. Vadhan (2009). Unbalanced expanders and randomness extractors from Parvaresh\u2013Vardy codes. J. ACM 56(4).","DOI":"10.1145\/1538902.1538904"},{"key":"71_CR14","doi-asserted-by":"crossref","unstructured":"Thomas Holenstein (2007). Parallel repetition: simplifications and the no-signaling case. In STOC, 411\u2013419.","DOI":"10.1145\/1250790.1250852"},{"key":"71_CR15","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo (1995). Hard-Core Distributions for Somewhat Hard Problems. In FOCS, 538\u2013545.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"71_CR16","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets & Avi Wigderson (2008). Uniform direct product theorems: simplified, optimized, and derandomized. In STOC, 579\u2013588.","DOI":"10.1145\/1374376.1374460"},{"key":"71_CR17","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P =\u00a0BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In STOC, 220\u2013229.","DOI":"10.1145\/258533.258590"},{"key":"71_CR18","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication Complexity. Cambridge University Press.","DOI":"10.1016\/S0065-2458(08)60342-3"},{"issue":"2","key":"71_CR19","first-page":"204","volume":"15","author":"Dror Lapidot","year":"1995","unstructured":"Dror Lapidot, Adi Shamir (1995) A One-Round, Two-Prover, Zero-Knowledge Protocol for NP. Combinatorica 15(2): 204\u2013214","journal-title":"Combinatorica"},{"key":"71_CR20","doi-asserted-by":"crossref","unstructured":"Noam Nisan, Steven Rudich & Michael E. Saks (1999). Products and Help Bits in Decision Trees. SIAM J. Comput. 28(3), 1035\u20131050.","DOI":"10.1137\/S0097539795282444"},{"issue":"1","key":"71_CR21","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"Noam Nisan","year":"1996","unstructured":"Noam Nisan, David Zuckerman (1996) Randomness is Linear in Space. J. Comput. Syst. Sci. 52(1): 43\u201352","journal-title":"J. Comput. Syst. Sci."},{"key":"71_CR22","doi-asserted-by":"crossref","unstructured":"Itzhak Parnafes, Ran Raz & Avi Wigderson (1997). Direct Product Results and the GCD Problem, in Old and New Communication Models. In STOC, 363\u2013372.","DOI":"10.1145\/258533.258620"},{"key":"71_CR23","doi-asserted-by":"crossref","unstructured":"Anup Rao (2008). Parallel repetition in projection games and a concentration bound. In STOC, 1\u201310.","DOI":"10.1145\/1374376.1374378"},{"issue":"3","key":"71_CR24","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"Ran Raz","year":"1998","unstructured":"Ran Raz (1998) A Parallel Repetition Theorem. SIAM J. Comput. 27(3): 763\u2013803","journal-title":"SIAM J. Comput."},{"key":"71_CR25","doi-asserted-by":"crossref","unstructured":"Ran Raz (2008). A Counterexample to Strong Parallel Repetition. In FOCS, 369\u2013373.","DOI":"10.1109\/FOCS.2008.49"},{"issue":"1-2","key":"71_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-003-0175-x","volume":"12","author":"Ronen Shaltiel","year":"2003","unstructured":"Ronen Shaltiel (2003) Towards proving strong direct product theorems. Computational Complexity 12(1-2): 1\u201322","journal-title":"Computational Complexity"},{"key":"71_CR27","doi-asserted-by":"crossref","unstructured":"Oleg Verbitsky (1994). Towards the Parallel Repetition Conjecture. In Structure in Complexity Theory Conference, 304\u2013307.","DOI":"10.1109\/SCT.1994.315794"},{"key":"71_CR28","unstructured":"Andrew C. Yao (1982). Theory and Applications of Trapdoor Functions (Extended Abstract). In FOCS, 80\u201391."},{"key":"71_CR29","unstructured":"Andrew Chi-Chih Yao (1979). Some Complexity Questions Related to Distributive Computing. In STOC, 209\u2013213."},{"issue":"4","key":"71_CR30","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z","volume":"11","author":"David Zuckerman","year":"1997","unstructured":"David Zuckerman (1997) Randomness-optimal oblivious sampling. Random Struct. Algorithms 11(4): 345\u2013367","journal-title":"Random Struct. Algorithms"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0071-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-013-0071-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0071-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T16:11:52Z","timestamp":1595952712000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-013-0071-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,18]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["71"],"URL":"https:\/\/doi.org\/10.1007\/s00037-013-0071-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6,18]]}}}