A linear lower bound on the unbounded error probabilistic communication complexity

Abstract

The main mathematical result of this paper may be stated as follows: Given a matrix M∈{−1,1}n×n and any matrix M̃∈Rn×n such that sign(M̃i,j)=Mi,j for all i,j, then rank(M̃)⩾n/||M||. Here ||M|| 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.