Lifting Dichotomies

Abstract Lifting theorems are used to transfer lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure $$A$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>A</mml:mi> </mml:math> for some function $$f$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>f</mml:mi> </mml:math> , we compose $$f$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>f</mml:mi> </mml:math> with a carefully chosen gadget function $$g$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>g</mml:mi> </mml:math> and get essentially the same lower bound on a complexity measure $$B$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>B</mml:mi> </mml:math> for the lifted function $$f \diamond g$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>⋄</mml:mo> <mml:mi>g</mml:mi> </mml:mrow> </mml:math> . Lifting theorems have applications in many different areas, such as circuit complexity, communication complexity, proof complexity, etc. One of the main questions in the context of lifting is how to choose a suitable gadget $$g$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>g</mml:mi> </mml:math> . Generally, 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 $$f$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>f</mml:mi> </mml:math> , 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. In this paper, we systematically study the question: ‘For which gadgets does the lifting result hold?’ in the following four settings: lifting from decision tree depth to decision tree size, lifting from conjunction DAG width to conjunction DAG size, lifting 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 gadgets by exposing the properties of gadgets that make lifting results hold. The structure of the results shows that there are no intermediate cases—for 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 $$f\diamond OR \diamond XOR$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>⋄</mml:mo> <mml:mi>O</mml:mi> <mml:mi>R</mml:mi> <mml:mo>⋄</mml:mo> <mml:mi>X</mml:mi> <mml:mi>O</mml:mi> <mml:mi>R</mml:mi> </mml:mrow> </mml:math> for some function $$f$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>f</mml:mi> </mml:math> .