{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:24:53Z","timestamp":1771485893838,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_61","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"749-760","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Local Reductions"],"prefix":"10.1007","author":[{"given":"Hamid","family":"Jahanjou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Miles","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"2","key":"61_CR1","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s00037-001-8191-1","volume":"10","author":"M Agrawal","year":"2001","unstructured":"Agrawal, M., Allender, E., Impagliazzo, R., Pitassi, T., Rudich, S.: Reducing the complexity of reductions. Computational Complexity 10(2), 117\u2013138 (2001)","journal-title":"Computational Complexity"},{"key":"61_CR2","doi-asserted-by":"crossref","unstructured":"Allender, E., Kouck\u00fd, M.: Amplifying lower bounds by means of self-reducibility. J. of the ACM, 57(3) (2010)","DOI":"10.1145\/1706591.1706594"},{"key":"61_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-02927-1_12","volume-title":"Automata, Languages and Programming","author":"S Arora","year":"2009","unstructured":"Arora, S., Steurer, D., Wigderson, A.: Towards a study of low-complexity graphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 119\u2013131. Springer, Heidelberg (2009)"},{"key":"61_CR4","first-page":"307","volume":"32","author":"KE Batcher","year":"1968","unstructured":"Batcher, K.E.: Sorting networks and their applications. AFIPS Spring Joint Computing Conference 32, 307\u2013314 (1968)","journal-title":"AFIPS Spring Joint Computing Conference"},{"key":"61_CR5","first-page":"45","volume":"19","author":"E Ben-Sasson","year":"2012","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete-efficiency threshold of probabilistically-checkable proofs. Electronic Colloquium on Computational Complexity (ECCC) 19, 45 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"61_CR6","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. (ITCS), pp. 401\u2013414 (2013)","DOI":"10.1145\/2422436.2422481"},{"key":"61_CR7","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":"61_CR8","doi-asserted-by":"crossref","unstructured":"Beame, P., Impagliazzo, R., Srinivasan, S.: Approximating AC $$^0$$ by small height decision trees and a deterministic algorithm for #AC $$^0$$ sat. In: IEEE Conf. on Computational Complexity (CCC), pp. 117\u2013125 (2012)","DOI":"10.1109\/CCC.2012.40"},{"key":"61_CR9","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 28, 337\u2013345 (1984)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"61_CR10","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R Beigel","year":"1994","unstructured":"Beigel, R., Tarui, J.: On ACC. Computational Complexity 4(4), 350\u2013366 (1994)","journal-title":"Computational Complexity"},{"key":"61_CR11","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Viola, E.: Short PCPs with projection queries (2014). http:\/\/www.ccs.neu.edu\/home\/viola\/","DOI":"10.1007\/978-3-662-43948-7_14"},{"key":"61_CR12","unstructured":"Calabro, C.: A lower bound on the size of series-parallel graphs dense in long paths. Electronic Colloquium on Computational Complexity (ECCC), 15(110) (2008)"},{"key":"61_CR13","unstructured":"Chen, R., Kabanets, V., Saurabh, N.: An improved deterministic #SAT algorithm for small De Morgan formulas. Technical Report TR13-150, Electronic Colloquium on Computational Complexity (2013). http:\/\/www.eccc.uni-trier.de\/"},{"issue":"5","key":"61_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0020-0190(88)90152-4","volume":"26","author":"SA Cook","year":"1988","unstructured":"Cook, S.A.: Short propositional formulas represent nondeterministic computations. Information Processing Letters 26(5), 269\u2013270 (1988)","journal-title":"Information Processing Letters"},{"issue":"1","key":"61_CR15","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E Dantsin","year":"2002","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch\u00f6ning, U.: A deterministic $$(2-2\/(k+1))n$$ algorithm for $$k$$ -SAT based on local search. Theoretical Computer Science 289(1), 69\u201383 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"61_CR16","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1145\/1101821.1101822","volume":"52","author":"L Fortnow","year":"2005","unstructured":"Fortnow, L., Lipton, R., van Melkebeek, D., Viglas, A.: Time-space lower bounds for satisfiability. J. of the ACM 52(6), 835\u2013865 (2005)","journal-title":"J. of the ACM"},{"key":"61_CR17","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"M Goldmann","year":"1992","unstructured":"Goldmann, M., H\u00e5stad, J., Razborov, A.A.: Majority gates vs. general weighted threshold gates. Computational Complexity 2, 277\u2013300 (1992)","journal-title":"Computational Complexity"},{"key":"61_CR18","doi-asserted-by":"crossref","unstructured":"Gurevich, Y., Shelah, S.: Nearly linear time. In: Logic at Botik, Symposium on Logical Foundations of Computer Science, pp. 108\u2013118 (1989)","DOI":"10.1007\/3-540-51237-3_10"},{"key":"61_CR19","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"},{"issue":"2","key":"61_CR20","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF01272517","volume":"1","author":"J H\u00e5stad","year":"1991","unstructured":"H\u00e5stad, J., Goldmann, M.: On the power of small-depth threshold circuits. Comput. Complexity 1(2), 113\u2013129 (1991)","journal-title":"Comput. Complexity"},{"issue":"2","key":"61_CR21","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0022-0000(93)90001-D","volume":"46","author":"A Hajnal","year":"1993","unstructured":"Hajnal, A., Maass, W., Pudl\u00e1k, P., Szegedy, M., Tur\u00e1n, G.: Threshold circuits of bounded depth. J. of Computer and System Sciences 46(2), 129\u2013154 (1993)","journal-title":"J. of Computer and System Sciences"},{"key":"61_CR22","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"F Hennie","year":"1966","unstructured":"Hennie, F., Stearns, R.: Two-tape simulation of multitape turing machines. J. of the ACM 13, 533\u2013546 (1966)","journal-title":"J. of the ACM"},{"key":"61_CR23","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"},{"key":"61_CR24","doi-asserted-by":"crossref","unstructured":"Iwama, K., Morizumi, H.: An explicit lower bound of $$5n - o(n)$$ for boolean circuits. In: Symp. on Math. Foundations of Computer Science (MFCS), pp. 353\u2013364 (2002)","DOI":"10.1007\/3-540-45687-2_29"},{"key":"61_CR25","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Matthews, W., Paturi, R.: A satisfiability algorithm for AC $$^{\\text{0 }}$$ . In: ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 961\u2013972 (2012)","DOI":"10.1137\/1.9781611973099.77"},{"issue":"2","key":"61_CR26","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$ -SAT. J. of Computer and System Sciences 62(2), 367\u2013375 (2001)","journal-title":"J. of Computer and System Sciences"},{"key":"61_CR27","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Schneider, S.: A satisfiability algorithm for sparse depth-2 threshold circuits. IEEE Symp. on Foundations of Computer Science (FOCS) (2013)","DOI":"10.1109\/FOCS.2013.58"},{"key":"61_CR28","unstructured":"Jahanjou, H., Miles, E., Viola, E.: Succinct and explicit circuits for sorting and connectivity (2014). http:\/\/www.ccs.neu.edu\/home\/viola\/"},{"key":"61_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/978-3-642-30870-3_44","volume-title":"How the World Computes","author":"AS Kulikov","year":"2012","unstructured":"Kulikov, A.S., Melanich, O., Mihajlin, I.: A 5n $$-$$ o(n) lower bound on the circuit size over U $$_\\text{2 }$$ of a linear boolean function. In: Cooper, S.B., Dawar, A., L\u00f6we, B. (eds.) CiE 2012. LNCS, vol. 7318, pp. 432\u2013439. Springer, Heidelberg (2012)"},{"key":"61_CR30","doi-asserted-by":"crossref","unstructured":"Lachish, O., Raz, R.: Explicit lower bound of 4.5n - o(n) for boolena circuits. In: ACM Symp. on the Theory of Computing (STOC), pp. 399\u2013408 (2001)","DOI":"10.1145\/380752.380832"},{"issue":"3\u20134","key":"61_CR31","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. 56(3\u20134), 313\u2013338 (2009)","journal-title":"Ann. Math. Artif. Intell."},{"key":"61_CR32","doi-asserted-by":"crossref","unstructured":"Makino, K., Tamaki, S., Yamamoto, M.: Derandomizing HSSW algorithm for 3-SAT (2011). CoRR, abs\/1102.3766","DOI":"10.1007\/978-3-642-22685-4_1"},{"key":"61_CR33","unstructured":"Oliveira, I.C.: Algorithms versus circuit lower bounds (2013). CoRR, abs\/1309.0249"},{"issue":"2","key":"61_CR34","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N Pippenger","year":"1979","unstructured":"Pippenger, N., Fischer, M.J.: Relations among complexity measures. J. of the ACM 26(2), 361\u2013381 (1979)","journal-title":"J. of the ACM"},{"issue":"3","key":"61_CR35","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R Paturi","year":"2005","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-sat. J. of the ACM 52(3), 337\u2013364 (2005)","journal-title":"J. of the ACM"},{"key":"61_CR36","doi-asserted-by":"crossref","unstructured":"Polishchuk, A., Spielman, D.A.: Nearly-linear size holographic proofs. In: ACM Symp. on the Theory of Computing (STOC), pp. 194\u2013203 (1994)","DOI":"10.1145\/195058.195132"},{"issue":"1","key":"61_CR37","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(91)90177-4","volume":"82","author":"JM Robson","year":"1991","unstructured":"Robson, J.M.: An O(T log T) reduction from RAM computations to satisfiability. Theoretical Computer Science 82(1), 141\u2013149 (1991)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"61_CR38","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"WL Ruzzo","year":"1981","unstructured":"Ruzzo, W.L.: On uniform circuit complexity. J. of Computer and System Sciences 22(3), 365\u2013383 (1981)","journal-title":"J. of Computer and System Sciences"},{"issue":"1","key":"61_CR39","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1145\/322047.322060","volume":"25","author":"C-P Schnorr","year":"1978","unstructured":"Schnorr, C.-P.: Satisfiability is quasilinear complete in NQL. J. of the ACM 25(1), 136\u2013145 (1978)","journal-title":"J. of the ACM"},{"key":"61_CR40","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1090\/S0025-5718-1992-1106981-9","volume":"58","author":"V Shoup","year":"1992","unstructured":"Shoup, V.: Searching for primitive roots in finite fields. Math. Comp. 58, 369\u2013380 (1992)","journal-title":"Math. Comp."},{"key":"61_CR41","first-page":"59","volume":"19","author":"R Santhanam","year":"2012","unstructured":"Santhanam, R., Williams, R.: Uniform circuits, lower bounds, and qbf algorithms. Electronic Colloquium on Computational Complexity (ECCC) 19, 59 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"61_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-08353-7_135","volume-title":"Mathematical Foundations of Computer Science 1977","author":"LG Valiant","year":"1977","unstructured":"Valiant, L.G.: Graph-theoretic arguments in low-level complexity. In: Gruska, J. (ed.) MFCS 1977. LNCS, vol. 53, pp. 162\u2013176. Springer, Heidelberg (1977)"},{"key":"61_CR43","unstructured":"Viola, E.: Challenges in computational lower bounds (2013). http:\/\/www.ccs.neu.edu\/home\/viola\/"},{"issue":"3","key":"61_CR44","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1561\/0400000012","volume":"2","author":"D van Melkebeek","year":"2006","unstructured":"van Melkebeek, D.: A survey of lower bounds for satisfiability and related problems. Foundations and Trends in Theoretical Computer Science 2(3), 197\u2013303 (2006)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"61_CR45","unstructured":"Viola, E., NEU. From RAM to SAT (2012). http:\/\/www.ccs.neu.edu\/home\/viola\/"},{"key":"61_CR46","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to circuit complexity","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to circuit complexity. Springer-Verlag, Berlin (1999)"},{"issue":"3","key":"61_CR47","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1145\/2034575.2034591","volume":"42","author":"R Williams","year":"2011","unstructured":"Williams, R.: Guest column: a casual tour around a circuit complexity bound. SIGACT News 42(3), 54\u201376 (2011)","journal-title":"SIGACT News"},{"key":"61_CR48","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":"61_CR49","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 42(3), 1218\u20131244 (2013)","journal-title":"SIAM J. on Computing"},{"key":"61_CR50","doi-asserted-by":"crossref","unstructured":"Williams, R.: Natural proofs versus derandomization. In: ACM Symp. on the Theory of Computing (STOC) (2013)","DOI":"10.1145\/2488608.2488612"},{"key":"61_CR51","doi-asserted-by":"crossref","unstructured":"Williams, R.: New algorithms and lower bounds for circuits with linear threshold gates (2014)","DOI":"10.1145\/2591796.2591858"},{"key":"61_CR52","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: On ACC and threshold circuits. In: IEEE Symp. on Foundations of Computer Science (FOCS), pp. 619\u2013627 (1990)","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_61","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:09:58Z","timestamp":1748459398000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}