{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:24:37Z","timestamp":1725686677448},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642308697"},{"type":"electronic","value":"9783642308703"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30870-3_44","type":"book-chapter","created":{"date-parts":[[2012,5,28]],"date-time":"2012-05-28T02:56:12Z","timestamp":1338173772000},"page":"432-439","source":"Crossref","is-referenced-by-count":1,"title":["A 5n\u2009\u2212\u2009o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function"],"prefix":"10.1007","author":[{"given":"Alexander S.","family":"Kulikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olga","family":"Melanich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"Mihajlin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"44_CR1","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":"44_CR2","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 \u2212 o(n) Lower Bound on the Circuit Complexity of Affine Dispersers. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol.\u00a06907, pp. 256\u2013265. Springer, Heidelberg (2011)"},{"key":"44_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/3-540-45687-2_29","volume-title":"Mathematical Foundations of Computer Science 2002","author":"K. Iwama","year":"2002","unstructured":"Iwama, K., Morizumi, H.: An Explicit Lower Bound of 5n-o(n) for Boolean Circuits. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 353\u2013364. Springer, Heidelberg (2002)"},{"key":"44_CR4","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":"44_CR5","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":"44_CR6","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":"44_CR7","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":"44_CR8","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":"44_CR9","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":"44_CR10","doi-asserted-by":"crossref","unstructured":"Lachish, O., Raz, R.: Explicit lower bound of 4.5n\u2009\u2212\u2009o(n) for boolean circuits. In: Proceedings of the Annual Symposium on Theory of Computing (STOC), pp. 399\u2013408 (2001)","DOI":"10.1145\/380752.380832"},{"key":"44_CR11","unstructured":"Hiltgen, A.P.L.: Cryptographically Relevant Contributions to Combinational Complexity Theory. ETH Series in Information Processing, vol. 3 (1994)"},{"key":"44_CR12","unstructured":"Lamagna, E.A., Savage, J.E.: On the logical complexity of symmeric switching functions in monotone and and complete bases. Technical report, Brown University (1973)"},{"issue":"2","key":"44_CR13","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF00289238","volume":"21","author":"N. Blum","year":"1984","unstructured":"Blum, N., Seysen, M.: Characterization of all optimal networks for a simultaneous computation of AND and NOR. Acta Informatica\u00a021(2), 171\u2013181 (1984)","journal-title":"Acta Informatica"},{"key":"44_CR14","first-page":"181","volume":"38","author":"N.P. Red\u2019kin","year":"1981","unstructured":"Red\u2019kin, N.P.: Minimal realization of a binary adder. Problemy kibernetiki\u00a038, 181\u2013216 (1981) (in Russian)","journal-title":"Problemy kibernetiki"},{"key":"44_CR15","unstructured":"Interlando, J.C., Byrne, E., Rosenthal, J.: The Gate Complexity of Syndrome Decoding of Hamming Codes. Applications of Computer Algebra (ACA), 1\u20135 (2004)"},{"issue":"2","key":"44_CR16","first-page":"43","volume":"6","author":"A.V. Chashkin","year":"1994","unstructured":"Chashkin, A.V.: On complexity of Boolean matrices, graphs and corresponding Boolean matrices. Diskretnaya Matematika\u00a06(2), 43\u201373 (1994) (in Russian)","journal-title":"Diskretnaya Matematika"}],"container-title":["Lecture Notes in Computer Science","How the World Computes"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30870-3_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:32:32Z","timestamp":1620127952000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30870-3_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642308697","9783642308703"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30870-3_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}