Name
Abstract | ||
|---|---|---|
We prove &thgr;(n log n) bounds for the deterministic 2-way communication complexity of the graph properties CONNECTIVITY, s-t-CONNECTIVITY and BIPARTITENESS (for arbitrary partitions of the variables into two sets of equal size). The proofs are based on combinatorial results of Dowling-Wilson and Lovász-Saks about partition matrices using the Möbius function, and the Regularity Lemma of Szemerédi. The bounds imply improved lower bounds for the VLSI complexity of these decision problems and sharp bounds for a generalized decision tree model which is related to the notion of evasiveness. |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1145/62212.62228 | STOC |
Keywords | Field | DocType |
decision problem,bius function,graph property,regularity lemma,equal size,arbitrary partition,n log n,combinatorial result,generalized decision tree model,vlsi complexity,2-way communication complexity,lower bound,decision tree,communication complexity | Discrete mathematics,Decision problem,Combinatorics,Graph property,Decision tree model,Communication complexity,Möbius function,Time complexity,Partition (number theory),Lemma (mathematics),Mathematics | Conference |
ISBN | Citations | PageRank |
0-89791-264-0 | 27 | 3.91 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| András Hajnal | 1 | 208 | 24.43 |
| Wolfgang Maass | 2 | 3717 | 391.51 |
| György Turán | 3 | 626 | 80.88 |