A well-studied class of functions in communication complexity are composed functions of the form f(g(x^1, y^1), ... , g(x^n,y^n)). This is a rich family of functions, which encompasses many of the examples studied in the literature. It is of great interest to understand what properties of f and g affect the communication complexity, and in what way. Say that g: X*Y --> {-1,+1} is strongly balanced if all rows and columns in the matrix [g(x,y)] sum to zero. We show that whenever g is strongly balanced and [g(x,y)] has rank at least two, the quantum communication complexity of f(g,...,g) is at least the approximate polynomial degree of f times the discrepancy bound of g under the uniform distribution. This result strictly generalizes the pattern matrix framework of Sherstov, which has been a very useful idea in a variety of settings. When g is strongly balanced and rank one, we show that the relevant lower bound is no longer approximate degree of f, but the approximate l1 norm of the Fourier coefficients of f --- the minimum l1 norm of the Fourier coefficients of a function which is entrywise close to f. We also enhance the framework of composed functions studied so far by considering functions f(g(x,y)), where the range of g is a group G. When G is Abelian, the analogue of the strongly balanced condition becomes a simple group invariance property of g. We are able to formulate a general lower bound on the communication complexity of f(g(x,y)) whenever g satisfies this property. Joint work with Troy Lee and Adi Shraibman

Date:	08:50-09:30, Wednesday, March 25, 2009

Venue:	FIT Building 1-315, Tsinghua University

Title:	Composition theorems in communication complexity

Speaker:	Shengyu Zhang

Biography:	Shengyu Zhang received his B.S. in MathematITCS at Fudan University in 1999, M.S. in Computer Science at Tsinghua University in 2002, and the Ph.D. in Computer Science at Princeton University in 2006. After working in NEC Laboratories America for a summer and in California Institute of Technology for a two-year postdoc, he joined The Chinese University of Hong Kong as an assistant professor in Department of Computer Science and Engineering. His main research interest is quantum computing, computational complexity such as query complexity and communication complexity, and algorithm designing especially on problems arising from practical networks.

Abstract:	A well-studied class of functions in communication complexity are composed functions of the form f(g(x^1, y^1), ... , g(x^n,y^n)). This is a rich family of functions, which encompasses many of the examples studied in the literature. It is of great interest to understand what properties of f and g affect the communication complexity, and in what way. Say that g: X*Y --> {-1,+1} is strongly balanced if all rows and columns in the matrix [g(x,y)] sum to zero. We show that whenever g is strongly balanced and [g(x,y)] has rank at least two, the quantum communication complexity of f(g,...,g) is at least the approximate polynomial degree of f times the discrepancy bound of g under the uniform distribution. This result strictly generalizes the pattern matrix framework of Sherstov, which has been a very useful idea in a variety of settings. When g is strongly balanced and rank one, we show that the relevant lower bound is no longer approximate degree of f, but the approximate l1 norm of the Fourier coefficients of f --- the minimum l1 norm of the Fourier coefficients of a function which is entrywise close to f. We also enhance the framework of composed functions studied so far by considering functions f(g(x,y)), where the range of g is a group G. When G is Abelian, the analogue of the strongly balanced condition becomes a simple group invariance property of g. We are able to formulate a general lower bound on the communication complexity of f(g(x,y)) whenever g satisfies this property. Joint work with Troy Lee and Adi Shraibman