<p>In notes, <a href="http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf" rel="nofollow">http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf</a>, it is mentioned towards end of section $4$ that <a href="http://dl.acm.org/citation.cfm?id=237817" rel="nofollow">http://dl.acm.org/citation.cfm?id=237817</a> shows that deterministic complexity of $CIS (\mathsf{Clique-IndependentSet})$ problem is $$D(CIS_G)\geq (2-o(1))n$$ with a specific graph $G$. I checked cited paper, it mentions no citation of $CIS_G$. However, it specifies a function for which $$D(f)\geq(2-o(1))n$$ holds in theorem $3$.</p>

<p>My question is how is this result connected to $CIS_G$? In other words how does lower bounds $D(f)$ on a function $f$ gives lower bounds on $CIS_G$ and/or vice versa?</p>

<p>What is best lower bound known for $D(CIS_G)$?</p>

CC BY-SA 3.0
2015-02-18T11:42:37.870Z
You might wish to look at [this paper](http://eccc.hpi-web.de/report/2015/012/) claiming an $\Omega(\log^{1.128} n)$ lower bound for CIS.
Stasys
CC BY-SA 3.0
2015-02-18T12:24:58.567Z
1.128 is indeed an interesting number on a paper. At a high level do you know how the proof works? Also how KLO paper relate to CISG?
Turbo
CC BY-SA 3.0
2015-02-18T19:54:56.790Z
Browsing through the literature, it is mentioned that KLO only implicitly prove a lower bound on $CIS_G$. It seems that the graph in question is bipartite $G = U \cup W$, Alice gets an edge $(x_1,y_1) \in U \times W$, and Bob gets a non-edge $(x_2,y_2) \in U \times W$. Hopefully these are enough hints to help you find out how their lower bound related to the clique vs. independent set problem.
Yuval Filmus
CC BY-SA 3.0
2015-02-18T22:13:43.050Z
oh nice. ok. I think one can think of char matrix as biadjacency. That should suffice I think.
Turbo
CC BY-SA 3.0
2015-02-20T21:16:07.240Z
@turbo: O.K., what he actually proves is that there are  boolean functions f such that, if k is the smallest number such that f can be written as an "unambiguous" k-DNF (where no input can evaluate to 1 more than one monomial), then every CNF for f must have a clause longer than k^{1.128}. Then he uses known results (including Yannakakis' ones) implying that this tradeoff already gives the desired lower bound for CIS. It would be nice to have a more *direct* proof. The connection to the KLO paper is explaned right here: KLO have tried to get a "direct proof".
Stasys
<graph-theory><lower-bounds><communication-complexity><clique>
$CIS_G$ problem deterministic lower bound
Turbo
# $CIS_G$ problem deterministic lower bound

(Asked by: username_0 on 2015-02-17)

In notes, <http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf>, it is mentioned towards end of section $4$ that <http://dl.acm.org/citation.cfm?id=237817> shows that deterministic complexity of $CIS (\mathsf{Clique-IndependentSet})$ problem is $$D(CIS\_G)\geq (2-o(1))n$$ with a specific graph $G$. I checked cited paper, it mentions no citation of $CIS\_G$. However, it specifies a function for which $$D(f)\geq(2-o(1))n$$ holds in theorem $3$.

My question is how is this result connected to $CIS\_G$? In other words how does lower bounds $D(f)$ on a function $f$ gives lower bounds on $CIS\_G$ and/or vice versa?

What is best lower bound known for $D(CIS\_G)$?

**Tags:** graph-theory, lower-bounds, communication-complexity, clique

> **Comments:**
> **username_1**: You might wish to look at [this paper](http://eccc.hpi-web.de/report/2015/012/) claiming an $\Omega(\log^{1.128} n)$ lower bound for CIS.  
> **username_0**: 1.128 is indeed an interesting number on a paper. At a high level do you know how the proof works? Also how KLO paper relate to CISG?  
> **username_2**: Browsing through the literature, it is mentioned that KLO only implicitly prove a lower bound on $CIS_G$. It seems that the graph in question is bipartite $G = U \cup W$, Alice gets an edge $(x_1,y_1) \in U \times W$, and Bob gets a non-edge $(x_2,y_2) \in U \times W$. Hopefully these are enough hints to help you find out how their lower bound related to the clique vs. independent set problem.  
> **username_0**: oh nice. ok. I think one can think of char matrix as biadjacency. That should suffice I think.  
> **username_1**: @turbo: O.K., what he actually proves is that there are  boolean functions f such that, if k is the smallest number such that f can be written as an "unambiguous" k-DNF (where no input can evaluate to 1 more than one monomial), then every CNF for f must have a clause longer than k^{1.128}. Then he uses known results (including Yannakakis' ones) implying that this tradeoff already gives the desired lower bound for CIS. It would be nice to have a more *direct* proof. The connection to the KLO paper is explaned right here: KLO have tried to get a "direct proof".  

---

## 0 answers

