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 ∈ {-1, 1}~(nxn) and any matrix M ∈ R~(nxn) such that sign(M_(i,j)) = M_(i,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.