{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:04:40Z","timestamp":1764781480781,"version":"3.46.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T00:00:00Z","timestamp":1761696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T00:00:00Z","timestamp":1761696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"abstract":"Abstract<\/jats:title>\n \n Lifting theorems are used to transfer lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure\n \n \n $$A$$<\/jats:tex-math>\n \n A<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for some function\n \n \n $$f$$<\/jats:tex-math>\n \n f<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we compose\n \n \n $$f$$<\/jats:tex-math>\n \n f<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n with a carefully chosen\n gadget<\/jats:italic>\n function\n \n \n $$g$$<\/jats:tex-math>\n \n g<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and get essentially the same lower bound on a complexity measure\n \n \n $$B$$<\/jats:tex-math>\n \n B<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for the\n lifted<\/jats:italic>\n function\n \n \n $$f \\diamond g$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \u22c4<\/mml:mo>\n g<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . \n Lifting theorems have applications in many different areas, such as circuit complexity, communication complexity, proof complexity, etc.\n <\/jats:p>\n \n One of the main questions in the context of lifting is how to choose a suitable gadget\n \n \n $$g$$<\/jats:tex-math>\n \n g<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\nGenerally, to get better results, i.e., to minimize the losses when transferring lower bounds, we need the gadget to be of a constant size (number of inputs). Unfortunately, in many settings we know lifting results only for gadgets of size that grows with the size of\n \n \n $$f$$<\/jats:tex-math>\n \n f<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and it is unclear whether they can be improved to constant-size gadgets. This motivates us to identify the properties of gadgets that make lifting possible.\n <\/jats:p>\n \n In this paper, we systematically study the question: \n\u2018For which gadgets\ndoes the lifting result hold?\u2019 in the following four settings: lifting from decision tree depth to decision tree size, \nlifting from conjunction DAG width to conjunction DAG size,\nlifting from decision tree depth to parity decision tree depth and size, and lifting from block sensitivity to deterministic and randomized communication complexities. In all the cases, we prove the complete classification of \ngadgets by exposing the properties of gadgets that make lifting results hold. The structure of the results shows that there are no intermediate cases\u2014for every gadget, there is either a polynomial lifting or no lifting at all. As a byproduct of our studies, we prove the log-rank conjecture for the class of functions that can be represented as\n \n \n $$f\\diamond OR \\diamond XOR$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \u22c4<\/mml:mo>\n O<\/mml:mi>\n R<\/mml:mi>\n \u22c4<\/mml:mo>\n X<\/mml:mi>\n O<\/mml:mi>\n R<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for some function\n \n \n $$f$$<\/jats:tex-math>\n \n f<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1007\/s00037-025-00276-5","type":"journal-article","created":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T06:04:20Z","timestamp":1761717860000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lifting Dichotomies"],"prefix":"10.1007","volume":"34","author":[{"given":"Yaroslav","family":"Alekseev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Filmus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander V.","family":"Smal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,29]]},"reference":[{"key":"276_CR1","doi-asserted-by":"publisher","unstructured":"Michael Alekhnovich, Jan Johannsen, Toniann Pitassi & Alasdair Urquhart (2007). An exponential separation between regular and general resolution. Theory Comput. 3, 81\u2013102. URL https:\/\/doi.org\/10.4086\/toc.2007.v003a005.","DOI":"10.4086\/toc.2007.v003a005"},{"key":"276_CR2","doi-asserted-by":"publisher","unstructured":"Yaroslav Alekseev, Yuval Filmus & Alexander Smal (2024). Lifting Dichotomies. In 39th Computational Complexity Conference, CCC 2024, July 22-25, 2024, Ann Arbor, MI, USA, Rahul Santhanam, editor, volume 300 of LIPIcs, 9:1\u20139:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2024.9.","DOI":"10.4230\/LIPIcs.CCC.2024.9"},{"key":"276_CR3","doi-asserted-by":"publisher","unstructured":"Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca & Ronald de Wolf (2001). Quantum Lower Bounds by Polynomials. J. ACM 48(4), 778\u2013797. ISSN 0004-5411. URL https:\/\/doi.org\/10.1145\/502090.502097.","DOI":"10.1145\/502090.502097"},{"key":"276_CR4","doi-asserted-by":"publisher","unstructured":"Paul Beame & Sajin Koroth (2023). On Disperser\/Lifting Properties of the Index and Inner-Product Functions. In 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, Yael Tauman Kalai, editor, volume 251 of LIPIcs, 14:1\u201314:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2023.14.","DOI":"10.4230\/LIPIcs.ITCS.2023.14"},{"key":"276_CR5","doi-asserted-by":"publisher","unstructured":"Eli Ben-Sasson & Avi Wigderson (2001). Short Proofs Are Narrow\u2014Resolution Made Simple. J. ACM 48(2), 149\u2013169. ISSN 0004-5411. URL https:\/\/doi.org\/10.1145\/375827.375835.","DOI":"10.1145\/375827.375835"},{"key":"276_CR6","doi-asserted-by":"crossref","unstructured":"A. Bernasconi & B. Codenotti (1999). Spectral analysis of Boolean functions as a graph eigenvalue problem. IEEE Transactions on Computers 48(3), 345\u2013351.","DOI":"10.1109\/12.755000"},{"key":"276_CR7","doi-asserted-by":"crossref","unstructured":"Harry Buhrman & Ronald de Wolf (2002). Complexity measures and decision tree complexity: a survey. Theoretical Computer Science 288(1), 21\u201343. ISSN 0304-3975. URL https:\/\/www.sciencedirect.com\/science\/article\/pii\/S030439750100144X. Complexity and Logic.","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"276_CR8","doi-asserted-by":"publisher","unstructured":"Arkadev Chattopadhyay, Michal Kouc\u1e31y, Bruno Loff & Sagnik Mukhopadhyay (2019). Simulation Theorems via Pseudo-Random Properties. Comput. Complex. 28(4), 617\u2013659. ISSN 1016-3328. URL https:\/\/doi.org\/10.1007\/s00037-019-00190-7.","DOI":"10.1007\/s00037-019-00190-7"},{"key":"276_CR9","unstructured":"Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal & Suhail Sherif (2023). Lifting to Parity Decision Trees via Stifling. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Yael Tauman Kalai, editor, volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), 33:1\u201333:20. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00a8ur Informatik, Dagstuhl, Germany. ISBN 978-3-95977-263-1. ISSN 1868-8969. URL https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ITCS.2023.33"},{"key":"276_CR10","doi-asserted-by":"publisher","unstructured":"Hubie Chen (2009). A Rendezvous of Logic, Complexity, and Algebra. ACM Comput. Surv. 42(1). ISSN 0360-0300. URL https:\/\/doi.org\/10.1145\/1592451.1592453.","DOI":"10.1145\/1592451.1592453"},{"key":"276_CR11","doi-asserted-by":"publisher","unstructured":"Ankit Garg, Mika G\u00f6\u00f6s, Pritish Kamath & Dmitry Sokolov (2020). Monotone circuit lower bounds from Resolution. Theory Comput. 16, Paper No. 13, 30. URL https:\/\/doi.org\/10.4086\/toc.2020.v016a013.","DOI":"10.4086\/toc.2020.v016a013"},{"key":"276_CR12","doi-asserted-by":"publisher","unstructured":"Mika G\u00f6\u00f6s, Shachar Lovett, Raghu Meka, Thomas Watson & David Zuckerman (2016). Rectangles Are Nonnegative Juntas. SIAM Journal on Computing 45(5), 1835\u20131869. URL https:\/\/doi.org\/10.1137\/15M103145X.","DOI":"10.1137\/15M103145X"},{"key":"276_CR13","doi-asserted-by":"publisher","unstructured":"Mika G\u00f6\u00f6s & Toniann Pitassi (2018). Communication lower bounds via critical block sensitivity. SIAM J. Comput. 47(5), 1778\u20131806. ISSN 0097-5397. URL https:\/\/doi.org\/10.1137\/16M1082007.","DOI":"10.1137\/16M1082007"},{"key":"276_CR14","doi-asserted-by":"publisher","unstructured":"Mika G\u00f6\u00f6s, Toniann Pitassi & ThomasWatson (2018). Deterministic Communication vs. Partition Number. SIAM Journal on Computing 47(6), 2435\u20132450. URL https:\/\/doi.org\/10.1137\/16M1059369.","DOI":"10.1137\/16M1059369"},{"key":"276_CR15","doi-asserted-by":"crossref","unstructured":"Mika G\u00f6\u00f6s, Toniann Pitassi & Thomas Watson (2017). Query-to-Communication Lifting for BPP. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 132\u2013143.","DOI":"10.1109\/FOCS.2017.21"},{"key":"276_CR16","doi-asserted-by":"publisher","unstructured":"Hamed Hatami, Kaave Hosseini & Shachar Lovett (2018). Structure of protocols for XOR functions. SIAM J. Comput. 47(1), 208\u2013217. ISSN 0097-5397. URL https:\/\/doi.org\/10.1137\/17M1136869.","DOI":"10.1137\/17M1136869"},{"key":"276_CR17","doi-asserted-by":"publisher","unstructured":"Trinh Huynh & Jakob Nordstr\u00f6m (2012). On the virtue of succinct proofs: amplifying communication complexity hardness to timespace trade-offs in proof complexity [extended abstract]. In STOC\u201912\u2014Proceedings of the 2012 ACM Symposium on Theory of Computing, 233\u2013247. ACM, New York. URL https:\/\/doi.org\/10.1145\/2213977.2214000.","DOI":"10.1145\/2213977.2214000"},{"key":"276_CR18","doi-asserted-by":"publisher","unstructured":"Alexander Knop, Shachar Lovett, Sam McGuire & Weiqiang Yuan (2021). Log-Rank and Lifting for AND-Functions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, 197\u2013208. Association for Computing Machinery, New York, NY, USA. ISBN 9781450380539. URL https:\/\/doi.org\/10.1145\/3406325.3450999.","DOI":"10.1145\/3406325.3450999"},{"key":"276_CR19","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1996). Communication Complexity. Cambridge University Press.","DOI":"10.1017\/CBO9780511574948"},{"key":"276_CR20","doi-asserted-by":"publisher","unstructured":"Shachar Lovett (2016). Communication is Bounded by Root of Rank. J. ACM 63(1). ISSN 0004-5411. URL https:\/\/doi.org\/10.1145\/2724704.","DOI":"10.1145\/2724704"},{"key":"276_CR21","unstructured":"Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi & Jiapeng Zhang (2022). Lifting with Sunflowers. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Mark Braverman, editor, volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), 104:1\u2013104:24. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. ISBN 978-3-95977-217-4. ISSN 1868-8969. URL https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2022\/15700."},{"key":"276_CR22","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz & Michael Saks (1988). Lattices, mobius functions and communications complexity. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, 81\u201390.","DOI":"10.1109\/SFCS.1988.21924"},{"key":"276_CR23","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz & Michael Saks (1993). Communication complexity and combinatorial lattice theory. Journal of Computer and System Sciences 47(2), 322\u2013349. ISSN 0022-0000. URL https:\/\/www.sciencedirect.com\/science\/article\/pii\/002200009390035U.","DOI":"10.1016\/0022-0000(93)90035-U"},{"key":"276_CR24","doi-asserted-by":"crossref","unstructured":"Ran Raz & Pierre Mckenzie (1999). Separation of the Monotone NC Hierarchy. Combinatorica 19.","DOI":"10.1007\/s004930050062"},{"key":"276_CR25","doi-asserted-by":"publisher","unstructured":"A. A. Razborov (1992). On the distributional complexity of disjointness. Theoret. Comput. Sci. 106(2), 385\u2013390. ISSN 0304-3975,1879-2294. URL https:\/\/doi.org\/10.1016\/0304-3975(92)90260-M.","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"276_CR26","doi-asserted-by":"crossref","unstructured":"Susanna de Rezende, Or Meir, Jakob Nordstrom, Toniann Pitassi, Robert Robere & Marc Vinyals (2020). Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 24\u201330.","DOI":"10.1109\/FOCS46700.2020.00011"},{"key":"276_CR27","doi-asserted-by":"crossref","unstructured":"Alexander A. Sherstov (2010). On quantum-classical equivalence for composed communication problems. Quantum Inf. Comput. 10(5-6), 435\u2013455. ISSN 1533-7146.","DOI":"10.26421\/QIC10.5-6-5"},{"key":"276_CR28","doi-asserted-by":"crossref","unstructured":"Alasdair Urquhart (2011). The Depth of Resolution Proofs. Studia Logica: An International Journal for Symbolic Logic 99(1\/3), 349\u2013364. ISSN 00393215, 15728730. URL http:\/\/www.jstor.org\/stable\/41475208.","DOI":"10.1007\/s11225-011-9356-9"},{"key":"276_CR29","doi-asserted-by":"publisher","unstructured":"Shengyu Zhang (2009). On the Tightness of the Buhrman\u2013Cleve\u2013Wigderson Simulation. In Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC \u201909, 434\u2013440. Springer-Verlag, Berlin, Heidelberg. ISBN 9783642106309. URL https:\/\/doi.org\/10.1007\/978-3-642-10631-6_45.","DOI":"10.1007\/978-3-642-10631-6_45"},{"key":"276_CR30","doi-asserted-by":"crossref","unstructured":"Zhiqiang Zhang & Yaoyun Shi (2010). On the parity complexity measures of Boolean functions. Theoretical Computer Science 411(26), 2612\u20132618. ISSN 0304-3975. URL https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397510001647","DOI":"10.1016\/j.tcs.2010.03.027"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00276-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00276-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00276-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:07Z","timestamp":1764781207000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00276-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,29]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["276"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00276-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,10,29]]},"assertion":[{"value":"27 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"18"}}