{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T00:45:22Z","timestamp":1777682722074,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439470","type":"print"},{"value":"9783662439487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_14","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"163-173","source":"Crossref","is-referenced-by-count":19,"title":["Short PCPs with Projection Queries"],"prefix":"10.1007","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"14_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms\u00a03(3), 289\u2013304 (1992)","journal-title":"Random Structures & Algorithms"},{"key":"14_CR2","unstructured":"Alon, N., Spencer, J.H., Erd\u0151s, P.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley and Sons, Inc. (1992)"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. In: ACM Innovations in Theoretical Computer Science Conf.\u00a0(ITCS), pp. 401\u2013414 (2013)","DOI":"10.1145\/2422436.2422481"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: ACM Symp. on the Theory of Computing (STOC), pp. 585\u2013594 (2013)","DOI":"10.1145\/2488608.2488681"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Short PCPs verifiable in polylogarithmic time. In: IEEE Conf. on Computational Complexity (CCC), pp. 120\u2013134 (2005)","DOI":"10.1109\/CCC.2005.27"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0304-3975(83)90029-4","volume":"28","author":"N. Blum","year":"1984","unstructured":"Blum, N.: A boolean function requiring 3n network size. Theoretical Computer Science\u00a028, 337\u2013345 (1984)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"14_CR7","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/050646445","volume":"38","author":"E. Ben-Sasson","year":"2008","unstructured":"Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM J.\u00a0on Computing\u00a038(2), 551\u2013607 (2008)","journal-title":"SIAM J.\u00a0on Computing"},{"issue":"4","key":"14_CR8","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. on Computing\u00a036(4), 889\u2013974 (2006)","journal-title":"SIAM J. on Computing"},{"issue":"4","key":"14_CR9","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"Cook, S.A.: A hierarchy for nondeterministic time complexity. J. of Computer and System Sciences\u00a07(4), 343\u2013353 (1973)","journal-title":"J. of Computer and System Sciences"},{"issue":"3","key":"14_CR10","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I. Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. of the ACM\u00a054(3), 12 (2007)","journal-title":"J. of the ACM"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Demenkov, E., Kulikov, A.S.: An elementary proof of a 3n\u2009\u2212\u2009o(n) lower bound on the circuit complexity of affine dispersers. In: Symp. on Math. Foundations of Computer Science (MFCS), pp. 256\u2013265 (2011)","DOI":"10.1007\/978-3-642-22993-0_25"},{"issue":"4","key":"14_CR12","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. on Computing\u00a036(4), 975\u20131024 (2006)","journal-title":"SIAM J. on Computing"},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"809","DOI":"10.4086\/toc.2013.v009a026","volume":"9","author":"B. Fefferman","year":"2013","unstructured":"Fefferman, B., Shaltiel, R., Umans, C., Viola, E.: On beating the hybrid argument. Theory of Computing\u00a09, 809\u2013843 (2013)","journal-title":"Theory of Computing"},{"issue":"2","key":"14_CR14","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00037-013-0068-6","volume":"22","author":"P. Gopalan","year":"2013","unstructured":"Gopalan, P., Meka, R., Reingold, O.: DNF sparsification and a faster deterministic counting algorithm. Computational Complexity\u00a022(2), 275\u2013310 (2013)","journal-title":"Computational Complexity"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Hertli, T.: 3-SAT faster and simpler - unique-SAT bounds for PPSZ hold in general. In: IEEE Symp. on Foundations of Computer Science (FOCS), pp. 277\u2013284 (2011)","DOI":"10.1109\/FOCS.2011.22"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: Exponential time vs. probabilistic polynomial time. In: IEEE Conf. on Computational Complexity (CCC) (2001)","DOI":"10.1016\/S0022-0000(02)00024-7"},{"issue":"4","key":"14_CR17","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"R. Impagliazzo","year":"2002","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: exponential time vs. probabilistic polynomial time. J. of Computer and System Sciences\u00a065(4), 672\u2013694 (2002)","journal-title":"J. of Computer and System Sciences"},{"key":"14_CR18","unstructured":"Jahanjou, H., Miles, E., Viola, E.: Local reductions (2013), http:\/\/www.ccs.neu.edu\/home\/viola\/"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Lipton, R.J.: Some connections between nonuniform and uniform complexity classes. In: ACM Symp. on the Theory of Computing (STOC), pp. 302\u2013309 (1980)","DOI":"10.1145\/800141.804678"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Luby, M., Veli\u010dkovi\u0107, B., Wigderson, A.: Deterministic approximate counting of depth-2 circuits. In: 2nd Israeli Symposium on Theoretical Computer Science (ISTCS), pp. 18\u201324 (1993)","DOI":"10.1109\/ISTCS.1993.253488"},{"issue":"3-4","key":"14_CR21","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s10472-009-9169-y","volume":"56","author":"T. Mie","year":"2009","unstructured":"Mie, T.: Short pcpps verifiable in polylogarithmic time with o(1) queries. Ann. Math. Artif. Intell.\u00a056(3-4), 313\u2013338 (2009)","journal-title":"Ann. Math. Artif. Intell."},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Makino, K., Tamaki, S., Yamamoto, M.: Derandomizing HSSW algorithm for 3-SAT. CoRR, abs\/1102.3766 (2011)","DOI":"10.1007\/978-3-642-22685-4_1"},{"key":"14_CR23","unstructured":"NEU. From RAM to SAT (2012), http:\/\/www.ccs.neu.edu\/home\/viola\/"},{"key":"14_CR24","doi-asserted-by":"crossref","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. In: 22nd ACM Symp. on the Theory of Computing (STOC), pp. 213\u2013223. ACM (1990)","DOI":"10.1145\/100216.100244"},{"key":"14_CR25","unstructured":"Oliveira, I.C.: Algorithms versus circuit lower bounds. CoRR, abs\/1309.0249 (2013)"},{"issue":"1","key":"14_CR26","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J.I. Seiferas","year":"1978","unstructured":"Seiferas, J.I., Fischer, M.J., Meyer, A.R.: Separating nondeterministic time complexity classes. J. of the ACM\u00a025(1), 146\u2013167 (1978)","journal-title":"J. of the ACM"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Santhanam, R., Williams, R.: On medium-uniformity and circuit lower bounds. In: IEEE Conf. on Computational Complexity (CCC) (2013)","DOI":"10.1109\/CCC.2013.40"},{"issue":"5","key":"14_CR28","doi-asserted-by":"publisher","first-page":"1387","DOI":"10.1137\/050640941","volume":"36","author":"E. Viola","year":"2007","unstructured":"Viola, E.: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM J. on Computing\u00a036(5), 1387\u20131403 (2007)","journal-title":"SIAM J. on Computing"},{"key":"14_CR29","unstructured":"Viola, E.: Challenges in computational lower bounds (2013), http:\/\/www.ccs.neu.edu\/home\/viola\/"},{"issue":"2-3","key":"14_CR30","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R. Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science\u00a0348(2-3), 357\u2013365 (2005)","journal-title":"Theoretical Computer Science"},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: 42nd ACM Symp. on the Theory of Computing (STOC), pp. 231\u2013240 (2010)","DOI":"10.1145\/1806689.1806723"},{"key":"14_CR32","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC circuit lower bounds. In: IEEE Conf. on Computational Complexity (CCC), pp. 115\u2013125 (2011)","DOI":"10.1109\/CCC.2011.36"},{"issue":"3","key":"14_CR33","doi-asserted-by":"publisher","first-page":"1218","DOI":"10.1137\/10080703X","volume":"42","author":"R. Williams","year":"2013","unstructured":"Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. SIAM J. on Computing\u00a042(3), 1218\u20131244 (2013)","journal-title":"SIAM J. on Computing"},{"key":"14_CR34","doi-asserted-by":"crossref","unstructured":"Williams, R.: New algorithms and lower bounds for circuits with linear threshold gates. In: ACM Symp. on the Theory of Computing, STOC (2014)","DOI":"10.1145\/2591796.2591858"},{"key":"14_CR35","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0304-3975(83)90015-4","volume":"26","author":"S. Z\u00e1k","year":"1983","unstructured":"Z\u00e1k, S.: A turing machine time hierarchy. Theoretical Computer Science\u00a026, 327\u2013333 (1983)","journal-title":"Theoretical Computer Science"}],"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-662-43948-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:10Z","timestamp":1746264670000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}