- Series
- Stochastics Seminar
- Time
- Thursday, December 2, 2010 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 002
- Speaker
- Santosh Vempala – College of Computing, Georgia Tech
- Organizer
- Yuri Bakhtin
For general graphs, approximating the maximum clique is a notoriously hard
problem even to approximate to a factor of nearly n, the number of vertices.
Does the situation get better with random graphs? A random graph on n
vertices where each edge is chosen with probability 1/2 has a clique of size
nearly 2\log n with high probability. However, it is not know how to find one
of size 1.01\log n in polynomial time. Does the problem become easier if a
larger clique were planted in a random graph? The current best algorithm can
find a planted clique of size roughly n^{1/2}. Given that any planted clique
of size greater than 2\log n is unique with high probability, there is a
large gap here. In an intriguing paper, Frieze and Kannan introduced a
tensor-based method that could reduce the size of the planted clique to as
small as roughly n^{1/3}. Their method relies on finding the spectral norm
of a 3-dimensional tensor, a problem whose complexity is open. Moreover,
their combinatorial proof does not seem to extend beyond this threshold. We
show how to recover the Frieze-Kannan result using a purely probabilistic
argument that generalizes naturally to r-dimensional tensors and allows us
recover cliques of size as small as poly(r).n^{1/r} provided we can find the
spectral norm of r-dimensional tensors. We highlight the algorithmic
question that remains open.
This is joint work with Charlie Brubaker.