BARC talk by Anup Rao

Friday, March 7, 2025, Anup Rao, Professor at the University of Washington, USA, will give a talk on "XOR lemmas for communication complexity".

Abstract:
If a function is hard to compute, is it even harder to compute it many times? In this talk Anup Rao will discuss this question in the context of communication complexity. He will explain two recent results:

  1. If f is a Boolean function with communication complexity c, then computing the n-fold xor of f evaluated on n inputs has communication complexity  n (Omega(sqrt(c)) - 1)).

  2. If f is a Boolean function with randomized communication complexity c, then computing the n-fold xor of f evaluated on n inputs with advantage exp(-n/100) has randomized communication complexity Omega( c sqrt(n)/ log(cn)).

Both results are joint work with Siddharth Iyer. The first result uses an additional observation of Guangxu Yang.

Portrait of Anup RaoBio:
Anup Rao is a professor of Computer Science at the University of Washington in Seattle, USA. His work is primarily in theoretical computer science, with an emphasis on computational complexity. From January-December of 2025, he is on sabbatical at UPC in Barcelona.

Host:
Amir Yehudayoff