Skip to Main Content

Fourier sparse functions and Log-rank XOR conjecture

This is a past event.

Friday, September 14, 2018 at 1:00pm to 2:00pm

CASE - Computing, Arts, Sciences & Education, 241
11200 SW 8th ST, Computing, Arts, Sciences & Education Miami, Florida 33199


Probably the most important open problem in communication complexity is the so-called "Log-rank conjecture", which asserts that the deterministic communication complexity of any two-party function F(x,y) is polynomially related to the rank of the corresponding communication matrix M_F. When F(x,y) has the nice symmetric property of F(x,y)=f(x+y), F is called an XOR function and the corresponding conjecture is known as the "Log-rank XOR conjecture". This conjecture is intimately connected to Boolean functions with sparse Fourier spectra. In this talk, I will discuss our recent results concerning the Log-rank XOR conjecture and properties of Fourier sparse Boolean functions.


Short bio:

Dr. Ning Xie received his Ph.D. in Computer Science in 2012 from MIT, his M.S. in Computer Science in 2002 from SUNY Buffalo, his M.S. in Theoretical Physics in 1996 from Fudan University in China and his B.E. in Shipbuilding Engineering in 1993 from Harbin Engineering University in China. Dr. Xie is currently an Assistant Professor in the School of Computing and Information Sciences at Florida International University (FIU). Prior to joining FIU, he was a postdoctoral fellow in MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) in 2012. Dr. Xie's research focuses on Fourier analysis of Boolean functions and sublinear algorithms (especially on property testing and local computation algorithms). 

Recent Activity