Abstract

Log-rank conjecture asserts that the communication complexity of a matrix is polynomially related to the logarithm of its rank. The general conjecture appears notoriously hard, and the last couple of years witnessed interestign progress of the conjecture on the special classes of XOR functions. In this talk, we’ll introduce the problem, survey some recent results, and suggest some seeming promising approaches.

Time

2017-06-14  14:50 ~ 15:35   

Speaker

Shengyu Zhang, The Chinese University of Hong Kong

Room

Room 102, No.100 Wudong Road, School of Information Management & Engineering, Shanghai University of Finance & Economics