3
$\begingroup$

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)$?

$\endgroup$
  • 3
    $\begingroup$ You might wish to look at this paper claiming an $\Omega(\log^{1.128} n)$ lower bound for CIS. $\endgroup$ – Stasys Feb 18 '15 at 11:42
  • $\begingroup$ 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? $\endgroup$ – Turbo Feb 18 '15 at 12:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 18 '15 at 19:54
  • $\begingroup$ oh nice. ok. I think one can think of char matrix as biadjacency. That should suffice I think. $\endgroup$ – Turbo Feb 18 '15 at 22:13
  • 1
    $\begingroup$ @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". $\endgroup$ – Stasys Feb 20 '15 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.