A linear lower bound on the unbounded error probabilistic communication complexity

The main mathematical result of this paper may be stated as follows: Given a matrix M is an element of {-1,1}(nxn) and any matrix (M) over tilde is an element of R-nxn such that sign ((M) over tilde)(i,j)) = M-i,M-j for all i,j, then rank((M) over tilde greater than or equal toparallel toMparallel to. Here parallel toMparallel to denotes the spectral norm of the matrix M. This implies a general lower bound on the complexity of unbounded error probabilistic communication protocols. As a simple consequence, we obtain the first linear lower bound on the complexity of unbounded error probabilistic communication protocols for the functions defined by Hadamard matrices. This solves a long-standing open problem stated by Paturi and Simon (J. Comput. System Sci. 33 (1986) 106). We also give an upper bound on the margin of any embedding of a concept class in half spaces. Such bounds are of interest to problems in learning theory. (C) 2002 Elsevier Science (USA). All rights reserved.