{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:55:57Z","timestamp":1757620557762,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":22,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819502141"},{"type":"electronic","value":"9789819502158"}],"license":[{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"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":[[2026]]},"DOI":"10.1007\/978-981-95-0215-8_14","type":"book-chapter","created":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T16:25:16Z","timestamp":1753979116000},"page":"179-192","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Nearly-$$4\\log n$$ Depth Lower Bound for\u00a0Formulas With Restriction on\u00a0Top"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1696-857X","authenticated-orcid":false,"given":"Hao","family":"Wu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,1]]},"reference":[{"key":"14_CR1","unstructured":"Bathie, G., Williams, R.R.: Towards stronger depth lower bounds. In: 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik (2024)"},{"key":"14_CR2","doi-asserted-by":"publisher","unstructured":"Cook, J., Mertz, I.: Tree evaluation is in space o(log n $$\\cdot $$ log log n). In: Mohar, B., Shinkar, I., O\u2019Donnell, R. (eds.) Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, 24\u201328 June 2024, pp. 1268\u20131278. ACM (2024). https:\/\/doi.org\/10.1145\/3618260.3649664","DOI":"10.1145\/3618260.3649664"},{"issue":"3","key":"14_CR3","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00037-017-0159-x","volume":"27","author":"I Dinur","year":"2017","unstructured":"Dinur, I., Meir, O.: Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity. Comput. Complex. 27(3), 375\u2013462 (2017). https:\/\/doi.org\/10.1007\/s00037-017-0159-x","journal-title":"Comput. Complex."},{"issue":"3","key":"14_CR4","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/s00037-001-8195-x","volume":"10","author":"J Edmonds","year":"2001","unstructured":"Edmonds, J., Impagliazzo, R., Rudich, S., Sgall, J.: Communication complexity towards lower bounds on circuit depth. Comput. Complex. 10(3), 210\u2013246 (2001). https:\/\/doi.org\/10.1007\/s00037-001-8195-x","journal-title":"Comput. Complex."},{"key":"14_CR5","doi-asserted-by":"publisher","unstructured":"Filmus, Y., Meir, O., Tal, A.: Shrinkage under random projections, and cubic formula lower bounds for AC0 (extended abstract). In: Lee, J.R. (ed.) 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, 6\u20138 January 2021, Virtual Conference. LIPIcs, vol.\u00a0185, pp. 89:1\u201389:7. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2021.89","DOI":"10.4230\/LIPIcs.ITCS.2021.89"},{"issue":"1","key":"14_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/15M1018319","volume":"46","author":"D Gavinsky","year":"2017","unstructured":"Gavinsky, D., Meir, O., Weinstein, O., Wigderson, A.: Toward better formula lower bounds: the composition of a function and a universal relation. SIAM J. Comput. 46(1), 114\u2013131 (2017). https:\/\/doi.org\/10.1137\/15M1018319","journal-title":"SIAM J. Comput."},{"key":"14_CR7","doi-asserted-by":"publisher","unstructured":"G\u00f6\u00f6s, M., Riazanov, A., Sofronova, A., Sokolov, D.: Top-down lower bounds for depth-four circuits. In: 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, 6\u20139 November 2023, pp. 1048\u20131055. IEEE (2023). https:\/\/doi.org\/10.1109\/FOCS57990.2023.00063","DOI":"10.1109\/FOCS57990.2023.00063"},{"issue":"1","key":"14_CR8","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 formulas is 2. SIAM J. Comput. 27(1), 48\u201364 (1998). https:\/\/doi.org\/10.1137\/S0097539794261556","journal-title":"SIAM J. Comput."},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J., Wigderson, A.: Composition of the universal relation. In: Advances in Computational Complexity Theory, AMS-DIMACS (1993)","DOI":"10.1090\/dimacs\/013\/07"},{"key":"14_CR10","doi-asserted-by":"publisher","unstructured":"Jukna, S.: Boolean Function Complexity - Advances and Frontiers, Algorithms and Combinatorics, vol.\u00a027. Springer, Cham (2012). https:\/\/doi.org\/10.1007\/978-3-642-24508-4","DOI":"10.1007\/978-3-642-24508-4"},{"issue":"3\/4","key":"14_CR11","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01206317","volume":"5","author":"M Karchmer","year":"1995","unstructured":"Karchmer, M., Raz, R., Wigderson, A.: Super-logarithmic depth lower bounds via the direct sum in communication complexity. Comput. Complex. 5(3\/4), 191\u2013204 (1995). https:\/\/doi.org\/10.1007\/BF01206317","journal-title":"Comput. Complex."},{"issue":"1","key":"14_CR12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1137\/15M1048045","volume":"46","author":"I Komargodski","year":"2017","unstructured":"Komargodski, I., Raz, R., Tal, A.: Improved average-case lower bounds for de Morgan formula size: Matching worst-case lower bound. SIAM J. Comput. 46(1), 37\u201357 (2017)","journal-title":"SIAM J. Comput."},{"issue":"48","key":"14_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.48","volume":"116","author":"S Koroth","year":"2018","unstructured":"Koroth, S., Meir, O.: Improved composition theorems for functions and relations. Leibniz Int. Proc. Inform. LIPIcs 116(48), 1\u201318 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.48","journal-title":"Leibniz Int. Proc. Inform. LIPIcs"},{"key":"14_CR14","doi-asserted-by":"publisher","unstructured":"Meir, O.: Toward better depth lower bounds: two results on the multiplexor relation. Comput. Complex. 29(1), 1\u201325 (2020). https:\/\/doi.org\/10.1007\/s00037-020-00194-8","DOI":"10.1007\/s00037-020-00194-8"},{"key":"14_CR15","doi-asserted-by":"publisher","unstructured":"Meir, O.: Toward better depth lower bounds: a KRW-like theorem for strong composition. In: 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, 6-9 November 2023, pp. 1056\u20131081. IEEE (2023). https:\/\/doi.org\/10.1109\/FOCS57990.2023.00064","DOI":"10.1109\/FOCS57990.2023.00064"},{"key":"14_CR16","unstructured":"Meir, O.: Personal Communication (2024)"},{"key":"14_CR17","doi-asserted-by":"publisher","unstructured":"Mihajlin, I., Smal, A.: Toward better depth lower bounds: the XOR-KRW conjecture. In: Kabanets, V. (ed.) 36th Computational Complexity Conference, CCC 2021, 20\u201323 July 2021, Toronto, Ontario, Canada (Virtual Conference). LIPIcs, vol.\u00a0200, pp. 38:1\u201338:24. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2021.38","DOI":"10.4230\/LIPIcs.CCC.2021.38"},{"key":"14_CR18","doi-asserted-by":"publisher","unstructured":"Mihajlin, I., Sofronova, A.: A better-than-3log(n) depth lower bound for de Morgan formulas with restrictions on top gates. In: Lovett, S. (ed.) 37th Computational Complexity Conference, CCC 2022, 20\u201323 July 2022, Philadelphia, PA, USA. LIPIcs, vol.\u00a0234, pp. 13:1\u201313:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.CCC.2022.13","DOI":"10.4230\/LIPICS.CCC.2022.13"},{"key":"14_CR19","doi-asserted-by":"publisher","unstructured":"de\u00a0Rezende, S.F., Meir, O., Nordstr\u00f6m, J., Pitassi, T., Robere, R.: KRW composition theorems via lifting. In: Irani, S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, 16\u201319 November 2020, pp. 43\u201349. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00013","DOI":"10.1109\/FOCS46700.2020.00013"},{"key":"14_CR20","doi-asserted-by":"publisher","unstructured":"Tal, A.: Shrinkage of de Morgan formulae by spectral techniques. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18\u201321 October 2014, pp. 551\u2013560. IEEE Computer Society (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.65","DOI":"10.1109\/FOCS.2014.65"},{"key":"14_CR21","unstructured":"Tal, A.: Computing requires larger formulas than approximating. Electron. Colloquium Comput. Complex. TR16-179 (2016)"},{"key":"14_CR22","unstructured":"Wu, H.: An improved composition theorem of a universal relation and most functions via effective restriction. Electron. Colloquium Comput. Complex. TR23-151 (2023)"}],"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-981-95-0215-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T09:33:29Z","timestamp":1757324009000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-0215-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,1]]},"ISBN":["9789819502141","9789819502158"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-0215-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,1]]},"assertion":[{"value":"1 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/cocoon2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}