Ning Xie
Florida International University
Lecture Information:
- September 14, 2018
- 1:00 PM
- ECS 241
Speaker 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).
Description
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.