Shengyu Zhang: Recent progress in studies of communication complexity of XOR functions

Shengyu Zhang, The Chinese University of Hong Kong

Abstract

Communication complexity of XOR functions f(x \oplus y) has recently drawn an increasing amount of attention. In this talk, I will discuss some recent progress on this interesting class of functions, including settling communication complexity of all symmetric XOR functions in one-way and SMP model, proving Log-rank conjecture for low-degree polynomials f, and showing tightness of a quantum lower bound in the two-way model.