A linear lower bound on the unbounded error probabilistic communication complexity

https://doi.org/10.1016/S0022-0000(02)00019-3Get rights and content
Under an Elsevier user license
open archive

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.

Keywords

Lower bounds
Probabilistic communication complexity
Hadamard matrix
Spectral norm

Cited by (0)