The planted clique problem and Nash games

Andreas Galanis, Subrahmanyam Kalyanasundaram, Anand Louis, Sarah Miracle, Amanda Streib, and Linji Yang are graduate students at Georgia Tech. Some are in the College of Computing, some in the College of Engineering, and some in the College of Science; all are co-authors on papers at the upcoming RANDOM 2011 Workshop.

Today I want to talk about one of the great open problems in complexity theory. It seems like we should be able to solve it, but it continues to elude us.

It is not ${\mathsf{P}}$ vs. ${\mathsf{NP}}$, nor graph isomorphism, nor factoring (my favorite problem), but is instead the planted clique problem. A paper by Per Austrin, Mark Braverman, and Eden Chlamtac at the simultaneous, co-located APPROX 2011 Workshop sheds some new light on this hard problem.

Georgia Tech did well at RANDOM—certainly having six graduate students on papers is a pretty terrific showing. I do not think this is a pure random event, as our faculty is very strong in this area. But it still is neat to see that we have done so well.

• Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions.
• Sarah Miracle, Dana Randall, and Amanda Streib. Clustering in Interfering Models of Binary Mixtures.
• Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, and Linji Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model.
• Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel Martin, Vojtěch Rödl, and Asaf Shapira. A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma.

I would be remiss if I did not point out that Subruk, Subrahmanyam Kalyanasundaram, is one of the co-authors of the last paper. Without his kind help, this blog would lose some perspective and certainly some writing quality. But I have said that before, have thanked him before, and will no doubt thank him again. I note that his paper is on removing randomness from an algorithm, and the main result is a de-randomization of a famous random algorithm by Alan Frieze and Ravi Kannan, which was one of the results cited in Kannan’s 2011 Knuth Prize.

Planting Cliques

Finding large cliques in an arbitrary graph is hard—of course, it is one of the earliest ${\mathsf{NP}}$-complete problems. Because the problem is hard, it is natural to try and make it “easier,” and that is what the planted clique problem attempts to do. Consider a random graph ${G(n,1/2)}$ on ${n}$ vertices that, as usual, has each edge selected with probability ${1/2}$ and independently. The expected size of its largest clique is long known to be

$\displaystyle (2 - o(1))\log n.$

The planted clique problem adds to a random ${G}$ a clique of size ${k}$. If ${k \gg \log n}$, one might guess that it should be possible to find the planted clique in polynomial time. Unfortunately this is only known to be possible when ${k}$ is order ${\sqrt n}$, as shown by Noga Alon, Michael Krivelevich, and Benny Sudakov in their 1998 paper.

Even small improvements to this bound seem to require some entirely new idea. I must admit to have spent some time thinking about this problem. But so far there has been no improvement to ${\Omega(\sqrt n)}$. The difficulty seems to be that while the clique is relatively large compared to the largest clique of the random part, there are many small cliques in the random part that help “hide” the planted clique.

Nash Games

Austrin, Braverman, and Chlamtac (ABC) continue a beautiful connection between the planted clique problem and finding Nash equilibria in two-player games that was discovered by Elad Hazan and Robert Krauthgamer. The latter showed roughly that finding a near-optimal Nash equilibrium is as hard as finding hidden cliques of size ${C \log n}$, for some universal constant ${C}$.

ABC continue this direction and show that other problems involving games are similarly related to the planted clique problem. For example, they show this for finding a second Nash equilibrium and finding a Nash equilibrium with small support. I like these results very much as they relate two of my favorite problems. I am unsure whether I should be more sure that the planted clique problem is hard.

One side-comment about the ABC paper: they reference our previous work, joint with Evangelos Markakis and Aranyak Mehta, on approximate Nash equilibria by calling it a

“a straightforward sampling argument.”

I agree that it is pretty simple—but. The “but” is that I recall when we worked on proving it, we were stuck for quite a while. We even almost gave up and moved on to another question, but somehow stayed with the question until it was solved. Once we had a proof it did seem simple. My point is not that I am bothered about ABC calling the result “straightforward,” but rather that sometimes simple results can be important. And further that sometimes they can be hard to find for the first time.

Open Problems

Think about solving the planted clique problem. It seems like it should be within our grasp—but perhaps not.

1. June 22, 2011 8:07 am

Maybe you got Linji’s picture wrong?

June 22, 2011 8:47 am

Linji is a guy, not a girl….

June 22, 2011 3:38 pm

Jian,

Sorry…copied wrong file

dick

3. June 22, 2011 12:42 pm

What is known about the “epsilon-“planted clique problem with random seed graph $G(N, \epsilon)$? We know that as $\epsilon$ tends to 0 the planted clique can approach constant size $\Omega(n^0)$. We also know that for $G(N, .5)$ a planted clique of size $\Omega(n^{.5})$ can be found in polynomial time. It seems natural to conjecture that a planted clique of size $\Omega(n^{\epsilon})$ on a random graph $G(n, \epsilon)$ can be found in polynomial time. A stronger conjecture is that these bounds are tight.

June 23, 2011 2:33 pm

I think that “straightforward” is actually great in this context. It
means that the ideas from the original construction have been
internalized and are now a standard tool. Simple techniques are so
important exactly because they can be easily remembered and reapplied.

By the way, the main takeaway message of the ABC paper is that there
does not seem to be a reduction from the original epsilon-Nash problem
to finding a hidden clique — at least at present. It appears that
finding a near-optimal Nash or a second Nash is qualitatively
different from finding just any epsilon-Nash. So it is still quite
possible that epsilon-Nash has a PTAS, while all other “flavors” of
the problem require quasi-polynomial time .