Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are known to require somewhat large gadgets.

We focus on one of the most widely used gadgets, the index gadget. For this gadget, existing lifting techniques are known to require at least a quadratic gadget size. We develop a new approach to prove lifting theorems for the indexing gadget, based on a novel connection to the recently developed robust sunflower lemmas. We show that this allows to reduce the gadget size to linear. We conjecture that it can be further improved to poly logarithmic, similar to the known bounds for the corresponding robust sunflower lemmas.