Random Remarks on RANDOM 2011
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 vs. , 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.
Finding large cliques in an arbitrary graph is hard—of course, it is one of the earliest -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 on vertices that, as usual, has each edge selected with probability and independently. The expected size of its largest clique is long known to be
The planted clique problem adds to a random a clique of size . If , 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 is order , 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 . 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.
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 , for some universal constant .
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.
Think about solving the planted clique problem. It seems like it should be within our grasp—but perhaps not.