Name
Abstract | ||
|---|---|---|
Halldórsson et al (ICALP proceedings of the 39th international colloquium conference on automata, languages, and programming, vol part I, Springer, pp 449–460, ) investigated the space complexity of the following problem CLIQUE-GAP(, ): given a graph stream , distinguish whether or , where is the clique-number of . In particular, they give matching upper and lower bounds for CLIQUE-GAP(, ) for any and , for some constant . The space complexity of the CLIQUE-GAP problem for smaller values of is left as an open question. In this paper, we answer this open question. Specifically, for any and for , we prove that the space complexity of CLIQUE-GAP problem is . Our lower bound is based on a new connection between graph decomposition theory (Chung et al in Studies in pure mathematics, Birkhäuser, Basel, pp 95–101, ; Chung in SIAM J Algebr Discrete Methods 2(1):1–12, ) and the multi-party set disjointness problem in communication complexity. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00453-017-0277-5 | Algorithmica |
Keywords | Field | DocType |
Communication complexity,Clique,Streaming algorithm,Graph decomposition,Triangle counting | Graph,Discrete mathematics,Combinatorics,Streaming algorithm,Clique,Upper and lower bounds,Communication complexity,Triangle counting,Omega,Mathematics | Conference |
Volume | Issue | ISSN |
80 | 2 | 0178-4617 |
Citations | PageRank | References |
0 | 0.34 | 18 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vladimir Braverman | 1 | 357 | 34.36 |
| Zaoxing Liu | 2 | 104 | 9.79 |
| Tejasvam Singh | 3 | 0 | 0.34 |
| N. V. Vinodchandran | 4 | 294 | 30.56 |
| Lin Yang | 5 | 31 | 21.21 |