One-way communication complexity of partial XOR functions

Boolean function F(x, y) is a XOR function if it can be represented as some function f of XOR of its inputs. XOR functions are relevant in communication complexity, because they encompass several other interesting functions, like functions based on Hamming distance and also for allowing Fourier analytic technique. For total XOR functions it is known that deterministic communication complexity of F is polynomially related to parity decision tree complexity of f and one-way communication complexity of F is exactly equal to non-adaptive parity decision tree complexity of f. We initiate the studies of a similar connection for partial functions. We show that in case of one-sided communication complexity whether these measures are equal, depends on the number of undefined inputs of f. We propose a Linear-algebraic framework which allows to prove both the equality for small enough number of undefined points and separation for large enough values. In particular, we provide a function with an exponential gap between these two measures. Our separation results translate to the case of two-sided communication complexity as well, in particular showing that the result of Hatami et al. (2018) cannot be generalized to partial functions. Joint work with Vladimir Podolskii (https://eccc.weizmann.ac.il/report/2023/157/).