{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T06:28:14Z","timestamp":1676960894879},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,3,28]],"date-time":"2014-03-28T00:00:00Z","timestamp":1395964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2015,6]]},"DOI":"10.1007\/s10208-014-9188-x","type":"journal-article","created":{"date-parts":[[2014,3,27]],"date-time":"2014-03-27T19:46:04Z","timestamp":1395949564000},"page":"651-680","source":"Crossref","is-referenced-by-count":5,"title":["The PCP Theorem for NP Over the Reals"],"prefix":"10.1007","volume":"15","author":[{"given":"Martijn","family":"Baartse","sequence":"first","affiliation":[]},{"given":"Klaus","family":"Meer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,3,28]]},"reference":[{"key":"9188_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.","DOI":"10.1017\/CBO9780511804090"},{"key":"9188_CR2","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems, J. ACM 45 (3), (1998), 501\u2013555. Extended abstract in Proc. of the 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1992, 14\u201323."},{"key":"9188_CR3","unstructured":"S. Arora and S. Safra, Probabilistic checking proofs: a new characterization of $$NP$$ N P , J. ACM 45 (1), (1998), 70\u2013122. Extended abstract in Proc. of the 33rd Annual Symposium on the Foundations of Computer Science, IEEE Computer Society, 1992, 2\u201313."},{"key":"9188_CR4","doi-asserted-by":"crossref","unstructured":"M. Baartse and K. Meer, Testing low degree trigonometric polynomials. Extended abstract in Proc. 9th International Computer Science Symposium in Russia CSR 2014, Moscow (N.K. Vereshchagin, E.A. Hirsch, S.O. Kuznetsov, and J.E. Pin, eds.), Springer LNCS, 2014.","DOI":"10.1007\/978-3-319-06686-8_7"},{"key":"9188_CR5","doi-asserted-by":"crossref","unstructured":"M. Baartse and K. Meer, Topics in real and complex number complexity theory, in Recent Advances in Real Complexity and Computation (J.L. Monta\u00f1a and L.M. Pardo, eds.), Contemporary Mathematics, vol. 604, American Mathematical Society (2013), 1\u201353.","DOI":"10.1090\/conm\/604\/12067"},{"key":"9188_CR6","unstructured":"M. Baartse and K. Meer, The PCP Theorem for NP over the Reals. Extended abstract in Proc. 30th Symposium on Theoretical Aspects of Computer Science STACS 2013 (N. Portier and T. Wilke, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 20, Schloss Dagstuhl - Leibniz Zentrum f\u00fcr Informatik (2013), pp. 104\u2013115, doi: 10.4230\/LIPIcs.STACS.2013.104 ."},{"key":"9188_CR7","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer, 1998.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"9188_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L Blum","year":"1989","unstructured":"L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers, NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc., vol. 21 (1989), 1\u201346.","journal-title":"Bull. Am. Math. Soc."},{"key":"9188_CR9","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1007\/BF01301968","volume":"29","author":"F Cucker","year":"1996","unstructured":"F. Cucker and M. Matamala, On digital nondeterminism. Mathematical Systems Theory 29 (1996), 635\u2013647.","journal-title":"Math. Syst. Theor."},{"key":"9188_CR10","doi-asserted-by":"crossref","unstructured":"F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther, On Real Turing Machines that Toss Coins, in Proceedings 27th Annual ACM Symposium on the Theory of Computing STOC (1995), 335\u2013342.","DOI":"10.1145\/225058.225155"},{"key":"9188_CR11","doi-asserted-by":"crossref","unstructured":"I. Dinur, The PCP theorem by gap amplification. J. ACM vol. 54 (3), Article 12 (2012). doi: 10.1145\/1236457.1236459 .","DOI":"10.1145\/1236457.1236459"},{"key":"9188_CR12","unstructured":"K. Friedl, Z. H\u00e1ts\u00e1gi and A. Shen, Low-Degree Tests, in Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms SODA (D.D. Sleator, ed.), 1994, 57\u201364."},{"key":"9188_CR13","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Basic Facts about Expander Graphs, in Studies in Complexity and Cryptography (O. Goldreich, ed.), Springer Lecture Notes in Computer Science 6650, 2011, 451\u2013464.","DOI":"10.1007\/978-3-642-22670-0_30"},{"key":"9188_CR14","doi-asserted-by":"crossref","unstructured":"K. Meer, Almost Transparent Short Proofs for NP $$_{\\mathbb{R}}$$ R , Extended abstract in Proc. 18th International Symposium on Fundamentals of Computation Theory FCT 2011 (O. Owe, M. Steffen, and J.A. Telle, eds.), Lecture Notes in Computer Science 6914, 2011, 41\u201352.","DOI":"10.1007\/978-3-642-22953-4_4"},{"issue":"3","key":"9188_CR15","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/s10208-005-0142-1","volume":"5","author":"K Meer","year":"2005","unstructured":"K. Meer, Transparent long proofs: a first PCP theorem for NP $$_{\\mathbb{R}}$$ R , , Vol. 5, Nr. 3 (2005), 231\u2013255.","journal-title":"Found. Comput. Math."},{"key":"9188_CR16","doi-asserted-by":"crossref","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O Reingold","year":"2002","unstructured":"O. Reingold, S. Vadhan, and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant degree expanders, Annals of Mathematics, vol. 155 (2002), 157\u2013187.","journal-title":"Ann. Math."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9188-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-014-9188-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9188-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,9]],"date-time":"2019-08-09T00:16:14Z","timestamp":1565309774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-014-9188-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,28]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["9188"],"URL":"https:\/\/doi.org\/10.1007\/s10208-014-9188-x","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3,28]]}}}