{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:14Z","timestamp":1725488954523},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_49","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"548-558","source":"Crossref","is-referenced-by-count":0,"title":["Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument"],"prefix":"10.1007","author":[{"given":"Rahul","family":"Tripathi","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"49_CR1","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1109\/CCC.2004.1313854","volume-title":"Proceedings of the 19th Annual IEEE Conference on Computational Complexity","author":"S. Aaronson","year":"2004","unstructured":"Aaronson, S.: Limitations of quantum advice and one-way communication. In: Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pp. 320\u2013332. IEEE Computer Society Press, Los Alamitos (2004)"},{"key":"49_CR2","unstructured":"Aaronson, S.: Quantum computing, postselection, and probabilistic polynomial-time. Technical Report 05-003, Electronic Colloquium on Computational Complexity (ECCC) (January 2005), \n                    \n                      http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"issue":"4","key":"49_CR3","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539704447237","volume":"35","author":"S. Aaronson","year":"2006","unstructured":"Aaronson, S.: Lower bounds for local search by quantum arguments. SIAM Journal on Computing\u00a035(4), 804\u2013824 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"49_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0022-0000(89)90018-4","volume":"39","author":"M. Abadi","year":"1989","unstructured":"Abadi, M., Feigenbaum, J., Kilian, J.: On hiding information from an oracle. Journal of Computer and System Sciences\u00a039(1), 21\u201350 (1989)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"49_CR5","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. Journal of the ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"Journal of the ACM"},{"key":"49_CR6","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1109\/SFCS.2003.1238195","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science","author":"D. Aharonov","year":"2003","unstructured":"Aharonov, D., Regev, O.: A lattice problem in quantum NP. In: Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 210\u2013219. IEEE Computer Society Press, Los Alamitos (2003)"},{"issue":"5","key":"49_CR7","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1145\/1089023.1089025","volume":"52","author":"D. Aharonov","year":"2005","unstructured":"Aharonov, D., Regev, O.: Lattice problems in NP \u2229 coNP. Journal of the ACM\u00a052(5), 749\u2013765 (2005)","journal-title":"Journal of the ACM"},{"issue":"1","key":"49_CR8","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of\u00a0NP. Journal of the ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"49_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0020-0190(87)90036-6","volume":"26","author":"L. Babai","year":"1987","unstructured":"Babai, L.: A random oracle separates PSPACE from the Polynomial Hierarchy. Information Processing Letters\u00a026(1), 51\u201353 (1987)","journal-title":"Information Processing Letters"},{"key":"49_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-52282-4_30","volume-title":"STACS 1990","author":"D. Beaver","year":"1990","unstructured":"Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol.\u00a0415, pp. 37\u201348. Springer, Heidelberg (1990)"},{"key":"49_CR11","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/s00037-006-0208-3","volume":"15","author":"R. Beigel","year":"2006","unstructured":"Beigel, R., Fortnow, L., Gasarch, W.: A tight lower bound for restricted PIR protocols. Computational Complexity\u00a015, 82\u201391 (2006)","journal-title":"Computational Complexity"},{"issue":"1","key":"49_CR12","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s001459900017","volume":"10","author":"D. Beaver","year":"1997","unstructured":"Beaver, D., Feigenbaum, J., Kilian, J., Rogaway, P.: Locally random reductions: Improvements and applications. Journal of Cryptology\u00a010(1), 17\u201336 (1997)","journal-title":"Journal of Cryptology"},{"issue":"1","key":"49_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity\u00a01(1), 3\u201340 (1991)","journal-title":"Computational Complexity"},{"issue":"1","key":"49_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M. Blum","year":"1995","unstructured":"Blum, M., Kannan, S.: Designing programs that check their work. Journal of the ACM\u00a042(1), 269\u2013291 (1995)","journal-title":"Journal of the ACM"},{"issue":"3","key":"49_CR15","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. Journal of Computer and System Sciences\u00a047(3), 549\u2013595 (1993)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"49_CR16","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing\u00a013(4), 850\u2013864 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"49_CR17","doi-asserted-by":"crossref","unstructured":"de Wolf, R.: Lower bounds on matrix rigidity via a quantum argument. In: Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming, pp. 62\u201371 (2006)","DOI":"10.1007\/11786986_7"},{"key":"49_CR18","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. Journal of the ACM\u00a043, 268\u2013292 (1996)","journal-title":"Journal of the ACM"},{"issue":"6","key":"49_CR19","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0020-0190(92)90104-4","volume":"44","author":"L. Fortnow","year":"1992","unstructured":"Fortnow, L., Szegedy, M.: On the power of two-local random reductions. Information Processing Letters\u00a044(6), 303\u2013306 (1992)","journal-title":"Information Processing Letters"},{"key":"49_CR20","first-page":"270","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer Security\u00a028, 270\u2013299 (1984)","journal-title":"Journal of Computer Security"},{"issue":"3","key":"49_CR21","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.jcss.2004.04.007","volume":"69","author":"I. Kerenidis","year":"2004","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. Journal of Computer and System Sciences\u00a069(3), 395\u2013420 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"49_CR22","unstructured":"Kerenidis, I.: Quantum multiparty communication complexity and circuit lower bounds. Technical Report quant-ph\/0504087, Los Alamos e-Print Quantum Physics Technical Report Archive (April 12, 2005)"},{"issue":"4","key":"49_CR23","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. Journal of the ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"Journal of the ACM"},{"key":"49_CR24","doi-asserted-by":"crossref","unstructured":"Lipton, R.: New directions in testing. In: Feigenbaum, J., Merritt, M. (eds.) Distributed Computing and Cryptography. DIMACS series in Discrete Mathematics and Theoretical Computer Science, pp. 191\u2013202. American Mathematical Society (1991)","DOI":"10.1090\/dimacs\/002\/13"},{"key":"49_CR25","first-page":"76","volume-title":"Proceedings of the 20th Annual IEEE Conference on Computational Complexity","author":"S. Laplante","year":"2005","unstructured":"Laplante, S., Lee, T., Szegedy, M.: The quantum adversary method and classical formula size lower bounds. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 76\u201390. IEEE Computer Society Press, Los Alamitos (2005)"},{"key":"49_CR26","first-page":"369","volume-title":"Proceedings of the 40th IEEE Symposium on Foundations of Computer Science","author":"A. Nayak","year":"1999","unstructured":"Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, pp. 369\u2013377. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"49_CR27","volume-title":"Quantum Computation and Quantum Information","author":"M. Nielsen","year":"2000","unstructured":"Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"49_CR28","doi-asserted-by":"crossref","unstructured":"Pavan, A., Vinodchandran, N.: 2-local random reductions to 3-valued functions. Computational Complexity (to appear)","DOI":"10.1007\/s00037-008-0245-1"},{"key":"49_CR29","volume-title":"Workshop on communication and computing","author":"R. Rivest","year":"1986","unstructured":"Rivest, R.: Workshop on communication and computing. MIT, Cambridge (1986)"},{"issue":"4","key":"49_CR30","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP=PSPACE. Journal of the ACM\u00a039(4), 869\u2013877 (1992)","journal-title":"Journal of the ACM"},{"key":"49_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1424","DOI":"10.1007\/11523468_115","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming","author":"S. Wehner","year":"2005","unstructured":"Wehner, S., de Wolf, R.: Improved lower bounds for locally decodable codes and private information retrieval. In: Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming. LNCS, pp. 1424\u20131436. Springer, Heidelberg (2005)"},{"key":"49_CR32","unstructured":"Yao, A.: An application of communication complexity to cryptography. In: Lecture at DIMACS Workshop on Structural Complexity and Cryptography (1990)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:29:17Z","timestamp":1619519357000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}