Siddharth Iyer: XOR lemmas and lifting in communication complexity скачать в хорошем качестве

Siddharth Iyer: XOR lemmas and lifting in communication complexity

Thursday Dec 11, 2025 XOR lemmas and lifting in communication complexity (Siddharth Iyer, Institute of Mathematics of the Czech Academy of Sciences) An XOR lemma states that if a Boolean function f is hard to compute, then computing the XOR of n copies of f is significantly harder. In this talk, I will discuss XOR lemmas for both randomized and deterministic communication complexity and a related lifting theorem for deterministic communication complexity. For randomized communication, we show that there is a constant c_0 such that if f(x,y) requires C ≥ c_0 bits to be computed with success probability 2/3, then computing the XOR of n copies of f with probability 1/2 + exp(-Ω(n)) — barely better than random guessing — requires communication at least Ω(sqrt{n} C / log(nC)). For deterministic communication, we show that there exists a constant c_0 such that if f requires C ≥ c_0 bits to be computed, then computing the XOR of n copies of f requires Ω(n sqrt{C}) bits. Lastly, I will discuss a lifting theorem, which generalizes the previous result and gives a lower bound on the communication required to compute the composition g(f(x_1,y_1),..,f(x_n,y_n)), where g is an arbitrary Boolean function. We show that there is a constant c_0 such that if f requires communication C ≥ c_0, then the communication required to compute the composition of g with f is at least Ω(min{s(g), deg(g)} sqrt{C}), where s(g) and deg(g) are the sensitivity and the degree of g respectively. These results are based on joint works with Anup Rao. In the first part of the talk, I will give an overview of the lifting theorem and in the second part, I will discuss the randomized XOR lemma. For more information about the MIAO seminars, please visit https://jakobnordstrom.se/miao-seminars/ .