{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T09:02:50Z","timestamp":1772442170583,"version":"3.50.1"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319905297","type":"print"},{"value":"9783319905303","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-90530-3_2","type":"book-chapter","created":{"date-parts":[[2018,4,24]],"date-time":"2018-04-24T07:23:53Z","timestamp":1524554633000},"page":"15-22","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bounds for Unrestricted Boolean Circuits: Open Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5656-0336","authenticated-orcid":false,"given":"Alexander S.","family":"Kulikov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,25]]},"reference":[{"key":"2_CR1","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24508-4","volume-title":"Boolean Function Complexity \u2013 Advances and Frontiers","author":"S Jukna","year":"2012","unstructured":"Jukna, S.: Boolean Function Complexity \u2013 Advances and Frontiers. Algorithms and Combinatorics. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-24508-4"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Find, M.G., Golovnev, A., Hirsch, E.A., Kulikov, A.S.: A better-than-3n lower bound for the circuit complexity of an explicit function. In: Dinur, I. (ed.) IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, NJ, USA, 9\u201311 October 2016, pp. 89\u201398. IEEE Computer Society (2016)","DOI":"10.1109\/FOCS.2016.19"},{"key":"2_CR3","unstructured":"Golovnev, A., Hirsch, E.A., Knop, A., Kulikov, A.S.: On the limits of gate elimination. [27], pp. 46:1\u201346:13"},{"key":"2_CR4","volume-title":"The Complexity of Boolean Functions","author":"I Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner, Hoboken (1987)"},{"key":"2_CR5","unstructured":"Lamagna, E.A., Savage, J.E.: On the logical complexity of symmetric switching functions in monotone and complete bases. Technical report, Brown University (1973)"},{"key":"2_CR6","unstructured":"Hiltgen, A.P.: Cryptographically relevant contributions to combinational complexity theory. Ph.D. thesis, ETH Zurich, Z\u00fcrich, Switzerland (1994)"},{"key":"2_CR7","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 Inf. 21, 171\u2013181 (1984)","journal-title":"Acta Inf."},{"key":"2_CR8","unstructured":"Melanich, O.: Technical report (2012)"},{"issue":"2","key":"2_CR9","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"},{"issue":"7","key":"2_CR10","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. Inf. Process. Lett. 110(7), 264\u2013267 (2010)","journal-title":"Inf. Process. Lett."},{"key":"2_CR11","doi-asserted-by":"publisher","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"},{"issue":"3","key":"2_CR12","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. Comput. 42(3), 1218\u20131244 (2013)","journal-title":"SIAM J. Comput."},{"key":"2_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1007\/978-3-662-47672-7_61","volume-title":"Automata, Languages, and Programming","author":"H Jahanjou","year":"2015","unstructured":"Jahanjou, H., Miles, E., Viola, E.: Local reductions. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 749\u2013760. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47672-7_61"},{"key":"2_CR14","unstructured":"Golovnev, A., Kulikov, A.S., Smal, A.V., Tamaki, S.: Circuit size lower bounds and #SAT upper bounds through a general framework. [27], pp. 45:1\u201345:16"},{"issue":"3","key":"2_CR15","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/3129173.3129180","volume":"4","author":"RR Williams","year":"2017","unstructured":"Williams, R.R.: Some ways of thinking algorithmically about impossibility. SIGLOG News 4(3), 28\u201340 (2017)","journal-title":"SIGLOG News"},{"issue":"1","key":"2_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"CE Shannon","year":"1949","unstructured":"Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell Syst. Tech. J. 28(1), 59\u201398 (1949)","journal-title":"Bell Syst. Tech. J."},{"issue":"6","key":"2_CR17","first-page":"558","volume":"15","author":"D Ulig","year":"1974","unstructured":"Ulig, D.: On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements. Math. Notes Acad. Sci. USSR 15(6), 558\u2013562 (1974)","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Exponential lower bounds for restricted monotone circuits. In: Johnson, D.S., Fagin, R., Fredman, M.L., Harel, D., Karp, R.M., Lynch, N.A., Papadimitriou, C.H., Rivest, R.L., Ruzzo, W.L., Seiferas, J.I. (eds.) Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, USA, 25\u201327 April 1983, pp. 110\u2013117. ACM (1983)","DOI":"10.1145\/800061.808739"},{"issue":"1","key":"2_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000033","volume":"5","author":"E Viola","year":"2009","unstructured":"Viola, E.: On the power of small-depth computation. Found. Trends Theor. Comput. Sci. 5(1), 1\u201372 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"2_CR20","first-page":"1171","volume":"111","author":"OB Lupanov","year":"1956","unstructured":"Lupanov, O.B.: On rectifier and switching-and-rectifier schemes. Dokl. Akad. Nauk SSSR 111, 1171\u20131174 (1956)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"2_CR21","first-page":"38","volume":"60","author":"D Grigoriev","year":"1976","unstructured":"Grigoriev, D.: An application of separability and independence notions for proving lower bounds of circuit complexity. Notes Sci. Semin. LOMI 60, 38\u201348 (1976)","journal-title":"Notes Sci. Semin. LOMI"},{"key":"2_CR22","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). https:\/\/doi.org\/10.1007\/3-540-08353-7_135"},{"issue":"1\u20132","key":"2_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000011","volume":"4","author":"SV Lokam","year":"2009","unstructured":"Lokam, S.V.: Complexity lower bounds using linear algebra. Found. Trends Theor. Comput. Sci. 4(1\u20132), 1\u2013155 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"1","key":"2_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000063","volume":"9","author":"S Jukna","year":"2013","unstructured":"Jukna, S., Sergeev, I.: Complexity of linear Boolean operators. Found. Trends Theor. Comput. Sci. 9(1), 1\u2013123 (2013)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"6","key":"2_CR25","first-page":"1302","volume":"139","author":"EI Nechiporuk","year":"1961","unstructured":"Nechiporuk, E.I.: Complexity of schemes in certain bases containing nontrivial elements with zero weights. Dokl. Akad. Nauk SSSR 139(6), 1302\u20131303 (1961)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/3-540-51083-4_47","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"CP Schnorr","year":"1989","unstructured":"Schnorr, C.P.: The multiplicative complexity of Boolean functions. In: Mora, T. (ed.) AAECC 1988. LNCS, vol. 357, pp. 45\u201358. Springer, Heidelberg (1989). https:\/\/doi.org\/10.1007\/3-540-51083-4_47"},{"key":"2_CR27","unstructured":"Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.): 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. LIPIcs, vol. 58, Krak\u00f3w, Poland, 22\u201326 August 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-90530-3_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T22:09:43Z","timestamp":1751580583000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-90530-3_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319905297","9783319905303"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-90530-3_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"25 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Moscow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}