Name
Title | ||
|---|---|---|
Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity |
Abstract | ||
|---|---|---|
Recently, Forster [7] proved a new lower bound on probabilistic communication complexity in terms of the operator norm of the communication matrix. In this paper, we want to exploit the various relations between communication complexity of distributed Boolean functions, geometric questions related to half space representations of these functions, and the computational complexity of these functions in various restricted models of computation. In order to widen the range of applicability of Forster's bound, we start with the derivation of a generalized lower bound. We present a concrete family of distributed Boolean functions where the generalized bound leads to a linear lower bound on the probabilistic communication complexity (and thus to an exponential lower bound on the number of Euclidean dimensions needed for a successful half space representation), whereas the old bound fails. We move on to a geometric characterization of the well known communication complexity class C-PP in terms of half space representations achieving a large margin. Our characterization hints to a close connection between the bounded error model of probabilistic communication complexity and the area of large margin classification. In the final section of the paper, we describe how our techniques can be used to prove exponential lower bounds on the size of depth-2 threshold circuits (with still some technical restrictions). Similar results can be obtained for read-k-times randomized ordered binary decision diagram and related models. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/3-540-45294-X_15 | FSTTCS |
Keywords | Field | DocType |
communication complexity class c-pp,boolean function,linear arrangements,space representation,computational complexity,generalized bound lead,probabilistic communication complexity,successful half space representation,communication matrix,communication complexity,lower bound,relational model,operator norm,model of computation | Complexity class,Asymptotic computational complexity,Discrete mathematics,Combinatorics,Upper and lower bounds,Computer science,Decision tree model,Communication complexity,Complexity index,Worst-case complexity,Game complexity,Distributed computing | Conference |
ISBN | Citations | PageRank |
3-540-43002-4 | 45 | 2.73 |
References | Authors | |
15 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jürgen Forster | 1 | 197 | 24.09 |
| Matthias Krause 0001 | 2 | 518 | 34.60 |
| Satyanarayana V. Lokam | 3 | 274 | 22.36 |
| rustam mubarakzjanov | 4 | 46 | 4.11 |
| Niels Schmitt | 5 | 83 | 10.79 |
| Hans-Ulrich Simon | 6 | 567 | 104.52 |