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)$?
$CIS_G$ problem deterministic lower bound
graph theory;lower bounds;communication complexity;clique