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}nn and any matrix such that for all i,j, then . 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.
lower bounds probabilistic communication complexity spectral norm hadamard matrix