Consider the following Communication Complexity problem: Alice is given a clique K, Bob is given a stable set S, and they have to decide via a non-deterministic protocol whether K intersects S or not. A certificate for the non-intersection is a bipartition of the vertices such that K is included in one side, and S is included in the other side. A Clique-Stable set Separator is a set of certificates which contains at least one suitable certificate for each input (K,S). Given a class of graphs, the goal is to know whether there exists, for every graph of the class, a Clique-Stable set Separator with only polynomially many certificates. This question, originally restricted to the case of perfect graphs, occurred to Yannakakis when studying extended formulations of the Stable set Polytope (a polytope P has a small extended formulation if it is the projection of a polytope Q lying in a higher dimensional space, with a small number of facets). A result by Göös provides a super-polynomial lower bound for the class of all graphs, but the case of perfect graphs is still open. We use different techniques to prove that a polynomial Clique-Stable set separator exists in restricted classes of graphs: probabilistic arguments for random graphs, VC-dimension for graphs where a split graph H is forbidden, and structural arguments for some other classes. We moreover highlight strong links between the Clique-Stable set Separation and other problems, including some Constraint Satisfaction Problems.