{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T09:02:49Z","timestamp":1772442169808,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642229923","type":"print"},{"value":"9783642229930","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22993-0_25","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T12:44:46Z","timestamp":1312893886000},"page":"256-265","source":"Crossref","is-referenced-by-count":20,"title":["An Elementary Proof of a 3n\u2009\u2212\u2009o(n) Lower Bound on the Circuit Complexity of Affine Dispersers"],"prefix":"10.1007","author":[{"given":"Evgeny","family":"Demenkov","sequence":"first","affiliation":[]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"C.E. Shannon","year":"1949","unstructured":"Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell System Technical Journal\u00a028, 59\u201398 (1949)","journal-title":"Bell System Technical Journal"},{"key":"25_CR2","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"},{"key":"25_CR3","unstructured":"Iwama, K., Lachish, O., Morizumi, H., Raz, R.: An explicit lower bound of 5n\u2009\u2212\u2009o(n) for boolean circuits (2005) (unpublished manuscript), \n                    \n                      http:\/\/www.wisdom.weizmann.ac.il\/~ranraz\/publications\/Podedl.ps"},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/1536414.1536426","volume-title":"Proceedings of the Annual Symposium on Theory of Computing (STOC)","author":"E. Ben-Sasson","year":"2009","unstructured":"Ben-Sasson, E., Kopparty, S.: Affine dispersers from subspace polynomials. In: Proceedings of the Annual Symposium on Theory of Computing (STOC), vol.\u00a0679, pp. 65\u201374. ACM Press, New York (2009)"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.tcs.2008.01.030","volume":"396","author":"J. Boyar","year":"2008","unstructured":"Boyar, J., Peralta, R.: Tight bounds for the multiplicative complexity of symmetric functions. Theoretical Computer Science\u00a0396, 223\u2013246 (2008)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"25_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(99)00182-6","volume":"235","author":"J. Boyar","year":"2000","unstructured":"Boyar, J., Peralta, R., Pochuev, D.: On The Multiplicative Complexity of Boolean Functions over the Basis \n                    \n                      \n                    \n                    $(\\land,\\oplus,1)$\n                  . Theoretical Computer Science\u00a0235(1), 1\u201316 (2000)","journal-title":"Theoretical Computer Science"},{"key":"25_CR7","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF02246615","volume":"13","author":"C.P. Schnorr","year":"1974","unstructured":"Schnorr, C.P.: Zwei lineare untere Schranken f\u00fcr die Komplexit\u00e4t Boolescher Funktionen. Computing\u00a013, 155\u2013171 (1974)","journal-title":"Computing"},{"issue":"3","key":"25_CR8","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0206030","volume":"6","author":"W.J. Paul","year":"1977","unstructured":"Paul, W.J.: A 2.5n-lower bound on the combinational complexity of Boolean functions. SIAM Journal of Computing\u00a06(3), 427\u2013433 (1977)","journal-title":"SIAM Journal of Computing"},{"key":"25_CR9","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF01683282","volume":"10","author":"L.J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.J.: On the combinational complexity of certain symmetric Boolean functions. Mathematical Systems Theory\u00a010, 323\u2013336 (1977)","journal-title":"Mathematical Systems Theory"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-13962-8_27","volume-title":"Programs, Proofs, Processes","author":"A. Kojevnikov","year":"2010","unstructured":"Kojevnikov, A., Kulikov, A.S.: Circuit Complexity and Multiplicative Complexity of Boolean Functions. In: Ferreira, F., L\u00f6we, B., Mayordomo, E., Mendes Gomes, L. (eds.) CiE 2010. LNCS, vol.\u00a06158, pp. 239\u2013245. Springer, Heidelberg (2010)"},{"key":"25_CR11","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 Journal on Computing\u00a020, 499\u2013505 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR12","unstructured":"Savicky, P., Zak, S.: A large lower bound for 1-branching programs. Technical Report TR96-036, ECCC (1996)"},{"key":"25_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-540-79228-4_30","volume-title":"Theory and Applications of Models of Computation","author":"K. Amano","year":"2008","unstructured":"Amano, K., Tarui, J.: A well-mixed function with circuit complexity 5n \u00b1o(n): Tightness of the lachish-raz-type bounds. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol.\u00a04978, pp. 342\u2013350. Springer, Heidelberg (2008)"},{"issue":"7","key":"25_CR14","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1016\/j.ipl.2010.01.007","volume":"110","author":"E. Demenkov","year":"2010","unstructured":"Demenkov, E., Kojevnikov, A., Kulikov, A.S., Yaroslavtsev, G.: New upper bounds on the Boolean circuit complexity of symmetric functions. Information Processing Letters\u00a0110(7), 264\u2013267 (2010)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22993-0_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T11:40:24Z","timestamp":1620042024000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22993-0_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229923","9783642229930"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22993-0_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}