Name
Abstract | ||
|---|---|---|
It is possible to view communication complexity as the minimum solution of an integer programming problem. This integer programming problem is relaxed to a linear programming problem and from it information regarding the original communication complexity question is deduced. A particularly appealing avenue this opens is the possibility of proving lower bounds on the communication complexity (which is a minimization problem) by exhibiting upper bounds on the maximization problem defined by the dual of the linear program. This approach works very neatly in the case of nondeterministic communication complexity. In this case a special case of Lovasz's fractional cover measure is obtained. Through it the amortized nondeterministic communication complexity is completely characterized. The power of the approach is also illustrated by proving lower and upper bounds on the nondeterministic communication complexity of various functions. In the case of deterministic complexity the situation is more complicated. Two attempts are discussed and some results using each of them are obtained. The main result regarding the first attempt is negative: one cannot use this method for proving superpolynomial lower bounds for formula size. The main result regarding the second attempt is a "direct-sum" theorem for two-round communication complexity. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1137/S0895480192238482 | SIAM J. Discrete Math. |
Keywords | DocType | Volume |
main result,nondeterministic communication complexity,fractional covers,two-round communication complexity,deterministic complexity,integer programming problem,original communication complexity question,lower bound,communication complexity,amortized nondeterministic communication complexity,upper bound,mathematics,computer science,boolean functions,linear programming,linear program,distributed algorithms,circuits,history,integer programming,protocols | Conference | 8 |
Issue | ISSN | ISBN |
1 | 0895-4801 | 0-8186-2955-X |
Citations | PageRank | References |
34 | 3.09 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mauricio Karchmer | 1 | 571 | 54.29 |
| Eyal Kushilevitz | 2 | 5525 | 478.96 |
| Noam Nisan | 3 | 8170 | 809.08 |