Randomized Lifting to Semi-Structured Communication Complexity

Lifting is a general technique which takes lower bounds for the complexity of some functions in a weak computational model and translates it into a bound for some new function in a stronger computational model. New function is obtained from the original one by combining it with some small gadget function. In this talk we will be interested in lifting from decision tree complexity to communication complexity. The major open problem in this area is to prove a lifting theorem for gadgets of constant size. The recent paper [Beame, Koroth, 2023] introduces semi-structured communication complexity, in which one of the players can only send parities of their input bits. They have shown that deterministic decision tree complexity can be lifted to semi-structured deterministic communication complexity using Indexing gadget of constant size. In this talk we will discuss the extension of this result to randomized case and to the larger family of gadgets. From our result it follows that deterministic/randomized decision tree complexity lifts to deterministic/randomized parity decision tree complexity. For randomized case this is the first result of this type. For deterministic case, our result improves the bound in [Chattopadhyay et al., 2023] for Inner Product gadget.
The talk is based on the joint paper with Alexander Shekhovtsov: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.78