𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A linear lower bound on the unbounded error probabilistic communication complexity

✍ Scribed by Jürgen Forster

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
187 KB
Volume
65
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

The main mathematical result of this paper may be stated as follows: Given a matrix MAfÀ1; 1g nÂn and any matrix MAR nÂn such that signð Mi;j Þ ¼ M i;j for all i; j; then rankð MÞXn=jjMjj: Here jjMjj 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.

📜 SIMILAR VOLUMES

A Probabilistic lower bound on the indep
A Probabilistic lower bound on the independence number of graphs
✍ Stanley M. Selkow 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 124 KB

Caro (1979) and Wei (1981) established a bound on the size of an independent set of a graph as a function of its degrees. In case the degrees of each vertex's neighbors are also known, we establish a lower bound which is tighter for most graphs.