{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T04:11:18Z","timestamp":1748491878611,"version":"3.41.0"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"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-319-21398-9_17","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"211-222","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits"],"prefix":"10.1007","author":[{"given":"Ruiwen","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentine","family":"Kabanets","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"issue":"4","key":"17_CR1","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. JACM 48(4), 778\u2013797 (2001)","journal-title":"JACM"},{"key":"17_CR2","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: Proceedings of the 2012 IEEE Conference on Computational Complexity, CCC 2012 (2012)","DOI":"10.1109\/CCC.2012.40"},{"key":"17_CR3","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":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s00039-007-0593-z","volume":"17","author":"J Bourgain","year":"2007","unstructured":"Bourgain, J.: On the construction of affine-source extractors. Geometric and Functional Analysis 17(1), 33\u201357 (2007)","journal-title":"Geometric and Functional Analysis"},{"key":"17_CR5","first-page":"184","volume":"21","author":"R Chen","year":"2014","unstructured":"Chen, R., Kabanets, V.: Correlation bounds and #sat algorithms for small linear-size circuits. ECCC 21, 184 (2014)","journal-title":"ECCC"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Chen, R., Kabanets, V., Kolokolova, A., Shaltiel, R., Zuckerman, D.: Mining circuit lower bound proofs for meta-algorithms. In: CCC 2014 (2014)","DOI":"10.1109\/CCC.2014.34"},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/978-3-662-44465-8_15","volume-title":"Mathematical Foundations of Computer Science 2014","author":"R Chen","year":"2014","unstructured":"Chen, R., Kabanets, V., Saurabh, N.: An improved deterministic #SAT algorithm for small de Morgan formulas. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 165\u2013176. Springer, Heidelberg (2014)"},{"key":"17_CR8","first-page":"99","volume":"21","author":"G Cohen","year":"2014","unstructured":"Cohen, G., Shinkar, I.: The complexity of DNF of parities. ECCC 21, 99 (2014)","journal-title":"ECCC"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-642-22993-0_25","volume-title":"Mathematical Foundations of Computer Science 2011","author":"E Demenkov","year":"2011","unstructured":"Demenkov, E., Kulikov, A.S.: An elementary proof of a 3n $$-$$ o(n) lower bound on the circuit complexity of affine dispersers. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 256\u2013265. Springer, Heidelberg (2011)"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: STOC 1986, pp. 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539794261556","volume":"27","author":"J H\u00e5stad","year":"1998","unstructured":"H\u00e5stad, J.: The shrinkage exponent of de Morgan formulae is 2. SIAM Journal on Computing 27, 48\u201364 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"17_CR12","first-page":"137","volume":"19","author":"J H\u00e5stad","year":"2012","unstructured":"H\u00e5stad, J.: On the correlation of parity and small-depth circuits. ECCC 19, 137 (2012)","journal-title":"ECCC"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Matthews, W., Paturi, R.: A satisfiability algorithm for AC$$^0$$. In: SODA 2012, pp. 961\u2013972 (2012)","DOI":"10.1137\/1.9781611973099.77"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Meka, R., Zuckerman, D.: Pseudorandomness from shrinkage. In: FOCS 2012, pp. 111\u2013119 (2012)","DOI":"10.1109\/FOCS.2012.78"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Iwama, K., Morizumi, H.: An explicit lower bound of $$5n - o(n)$$ for boolean circuits. In: MFCS 2002, pp. 353\u2013364 (2002)","DOI":"10.1007\/3-540-45687-2_29"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Raz, R.: Average-case lower bounds for formula size. In: STOC 2013, pp. 171\u2013180 (2013)","DOI":"10.1109\/FOCS.2013.69"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Raz, R., Tal, A.: Improved average-case lower bounds for demorgan formula size. In: FOCS 2013, pp. 588\u2013597 (2013)","DOI":"10.1109\/FOCS.2013.69"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"Lachish, O., Raz, R.: Explicit lower bound of $$4.5n - o(n)$$ for boolena circuits. In: STOC 2001, pp. 399\u2013408. ACM, New York (2001)","DOI":"10.1145\/380752.380832"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Li, X.: A new approach to affine extractors and dispersers. In: CCC 2011, pp. 137\u2013147 (2011)","DOI":"10.1109\/CCC.2011.27"},{"key":"17_CR20","unstructured":"Nurk, S.: An $$o(2^{0.4058m})$$ upper bound for circuit sat. PDMI Preprint (2009)"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"Reichardt, B.: Reflections for quantum query algorithms. In: SODA 2011, pp. 560\u2013569 (2011)","DOI":"10.1137\/1.9781611973082.44"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Santhanam, R.: Fighting perebor: new and improved algorithms for formula and qbf satisfiability. In: FOCS 2010, pp. 183\u2013192 (2010)","DOI":"10.1109\/FOCS.2010.25"},{"issue":"2","key":"17_CR23","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF02246615","volume":"13","author":"C Schnorr","year":"1974","unstructured":"Schnorr, C.: Zwei lineare untere schranken f\u00fcr die komplexit\u00e4t boolescher funktionen. Computing 13(2), 155\u2013171 (1974)","journal-title":"Computing"},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"Seto, K., Tamaki, S.: A satisfiability algorithm and average-case hardness for formulas over the full binary basis. In: CCC 2012, pp. 107\u2013116 (2012)","DOI":"10.1109\/CCC.2012.29"},{"key":"17_CR25","first-page":"110","volume":"2","author":"BA Subbotovskaya","year":"1961","unstructured":"Subbotovskaya, B.A.: Realizations of linear functions by formulas using and or, not. Soviet Math. Doklady 2, 110\u2013112 (1961)","journal-title":"Soviet Math. Doklady"},{"key":"17_CR26","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Separating the polynomial-time hierarchy by oracles. In: FOCS 1985, pp. 1\u201310 (1985)","DOI":"10.1109\/SFCS.1985.49"},{"issue":"2","key":"17_CR27","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00493-011-2604-9","volume":"31","author":"A Yehudayoff","year":"2011","unstructured":"Yehudayoff, A.: Affine extractors over prime fields. Combinatorica 31(2), 245\u2013256 (2011)","journal-title":"Combinatorica"},{"issue":"3","key":"17_CR28","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/0220032","volume":"20","author":"U Zwick","year":"1991","unstructured":"Zwick, U.: A 4n lower bound on the combinational complexity of certain symmetric boolean functions over the basis of unate dyadic boolean functions. SIAM J. Comput. 20(3), 499\u2013505 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T20:33:50Z","timestamp":1748464430000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}