{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T09:02:48Z","timestamp":1772442168999,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T00:00:00Z","timestamp":1414454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,5]]},"DOI":"10.1007\/s00224-014-9590-4","type":"journal-article","created":{"date-parts":[[2014,10,27]],"date-time":"2014-10-27T01:53:27Z","timestamp":1414374807000},"page":"630-642","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["New Lower Bounds on Circuit Size of Multi-output Functions"],"prefix":"10.1007","volume":"56","author":[{"given":"Evgeny","family":"Demenkov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","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","published-online":{"date-parts":[[2014,10,28]]},"reference":[{"key":"9590_CR1","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 28, 337\u2013345 (1984)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9590_CR2","doi-asserted-by":"crossref","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 21(2), 171\u2013181 (1984)","journal-title":"Informatica"},{"issue":"2","key":"9590_CR3","first-page":"43","volume":"6","author":"AV Chashkin","year":"1994","unstructured":"Chashkin, A.V.: On complexity of Boolean matrices, graphs and corresponding Boolean matrices. Diskretnaya matematika 6(2), 43\u201373 (1994). in Russian","journal-title":"Diskretnaya matematika"},{"key":"9590_CR4","doi-asserted-by":"crossref","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: Proceedings of 36th International Symposium on Mathematical Foundations of Computer Science (MFCS), Springer, Lecture Notes in Computer Science, Vol. 6907, pp 256\u2013265 (2011)","DOI":"10.1007\/978-3-642-22993-0_25"},{"issue":"4","key":"9590_CR5","first-page":"1","volume":"4","author":"SB Gashkov","year":"1994","unstructured":"Gashkov, S.B., Kochergin, V.V.: On addition chains of vectors, gate circuits, and the complexity of computations of powers. Sib. Adv. Math. 4(4), 1\u201316 (1994)","journal-title":"Sib. Adv. Math."},{"key":"9590_CR6","unstructured":"Hiltgen, A.P.L.: Cryptographically Relevant Contributions to Combinational Complexity Theory. ETH Series in Information Processing 3, doi: 10.3929\/ethz-a-000926139 (1994)"},{"key":"9590_CR7","doi-asserted-by":"crossref","unstructured":"Iwama, K., Morizumi, H.: An explicit lower bound of 5n \u2212 o(n) for boolean circuits. In: Proceedings of International Symposium on Mathematical Foundations of Computer Science (MFCS), Springer, Lecture Notes in Computer Science, vol. 2420, pp 353?364 (2002)","DOI":"10.1007\/3-540-45687-2_29"},{"key":"9590_CR8","doi-asserted-by":"crossref","unstructured":"Kojevnikov, A., Kulikov, A.S.: Circuit Complexity and Multiplicative Complexity of Boolean Functions. In: Proceedings of Computability in Europe (CiE), Springer, Lecture Notes in Computer Science, vol. 6158, pp 239?245 (2010)","DOI":"10.1007\/978-3-642-13962-8_27"},{"key":"9590_CR9","doi-asserted-by":"crossref","unstructured":"Lachish, O., Raz, R.: Explicit lower bound of 4.5n \u2212 o(n) for boolean circuits. In: Proceedings of the Annual Symposium on Theory of Computing (STOC), pp 399?408 (2001)","DOI":"10.1145\/380752.380832"},{"key":"9590_CR10","unstructured":"Lamagna, E.A., Savage, J.E.: On the logical complexity of symmetric switching functions in monotone and complete bases. Tech. rep., Brown University (1973)"},{"key":"9590_CR11","doi-asserted-by":"crossref","unstructured":"Muller, D.E.: Complexity in electronic switching circuits. IRE Transactions on Electronic Computers EC-5, 15\u201319 (1956)","DOI":"10.1109\/TEC.1956.5219786"},{"issue":"3","key":"9590_CR12","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1137\/0206030","volume":"6","author":"WJ Paul","year":"1977","unstructured":"Paul, W.J.: A 2.5n-lower bound on the combinational complexity of Boolean functions. SIAM J. Comput. 6(3), 427\u2013433 (1977)","journal-title":"SIAM J. Comput."},{"key":"9590_CR13","first-page":"181","volume":"38","author":"NP Red\u2019kin","year":"1981","unstructured":"Red\u2019kin, N.P.: Minimal realization of a binary adder. Problemy kibernetiki 38, 181\u2013216 (1981). in Russian","journal-title":"Problemy kibernetiki"},{"key":"9590_CR14","unstructured":"Savick\u00fd, P., \u017e\u00e1k, S.: A large lower bound for 1-branching programs. Tech. Rep. TR96-036, ECCC (1996)"},{"key":"9590_CR15","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02246615","volume":"13","author":"CP Schnorr","year":"1974","unstructured":"Schnorr, C.P.: Zwei lineare untere Schranken f\u00fcr die Komplexit\u00e4t Boolescher Funktionen. Computing 13, 155\u2013171 (1974)","journal-title":"Computing"},{"key":"9590_CR16","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0304-3975(76)90073-6","volume":"1","author":"CP Schnorr","year":"1976","unstructured":"Schnorr, C.P.: The combinational complexity of equivalence. Theor. Comput. Sci. 1, 289\u2013295 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"9590_CR17","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF01683282","volume":"10","author":"LJ Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.J.: On the combinational complexity of certain symmetric Boolean functions. Math. Syst. Theory 10, 323\u2013336 (1977)","journal-title":"Math. Syst. Theory"},{"key":"9590_CR18","doi-asserted-by":"crossref","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, 499\u2013505 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9590-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9590-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9590-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T13:19:49Z","timestamp":1565961589000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9590-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,28]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["9590"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9590-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,28]]}}}